home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: Mailbox/MIME Entity
(archive/mbox).
You can browse this item here: ALGORITH.114
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Mailbox/MIME Entity (archive/mbox)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| Mailbox text, 1st line "From jdstone@destin.dazixco.ingr.com Fri Oct 14 22:13:59 1994", ASCII text
| default
| |
| 100%
| TrID
| E-Mail message (Var. 2)
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| x-fmt/111 Plain Text File
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| application/mbox
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 6a 64 73 | 74 6f 6e 65 40 64 65 73 |From jds|tone@des|
|00000010| 74 69 6e 2e 64 61 7a 69 | 78 63 6f 2e 69 6e 67 72 |tin.dazi|xco.ingr|
|00000020| 2e 63 6f 6d 20 46 72 69 | 20 4f 63 74 20 31 34 20 |.com Fri| Oct 14 |
|00000030| 32 32 3a 31 33 3a 35 39 | 20 31 39 39 34 0a 46 72 |22:13:59| 1994.Fr|
|00000040| 6f 6d 3a 20 6a 64 73 74 | 6f 6e 65 40 64 65 73 74 |om: jdst|one@dest|
|00000050| 69 6e 2e 64 61 7a 69 78 | 63 6f 2e 69 6e 67 72 2e |in.dazix|co.ingr.|
|00000060| 63 6f 6d 20 28 4a 6f 6e | 20 53 74 6f 6e 65 29 0a |com (Jon| Stone).|
|00000070| 4e 65 77 73 67 72 6f 75 | 70 73 3a 20 63 6f 6d 70 |Newsgrou|ps: comp|
|00000080| 2e 67 72 61 70 68 69 63 | 73 2e 61 6c 67 6f 72 69 |.graphic|s.algori|
|00000090| 74 68 6d 73 2c 63 6f 6d | 70 2e 61 6e 73 77 65 72 |thms,com|p.answer|
|000000a0| 73 2c 6e 65 77 73 2e 61 | 6e 73 77 65 72 73 0a 53 |s,news.a|nswers.S|
|000000b0| 75 62 6a 65 63 74 3a 20 | 63 6f 6d 70 2e 67 72 61 |ubject: |comp.gra|
|000000c0| 70 68 69 63 73 2e 61 6c | 67 6f 72 69 74 68 6d 73 |phics.al|gorithms|
|000000d0| 20 46 72 65 71 75 65 6e | 74 6c 79 20 41 73 6b 65 | Frequen|tly Aske|
|000000e0| 64 20 51 75 65 73 74 69 | 6f 6e 73 20 28 46 41 51 |d Questi|ons (FAQ|
|000000f0| 29 0a 53 75 70 65 72 73 | 65 64 65 73 3a 20 3c 67 |).Supers|edes: <g|
|00000100| 72 61 70 68 69 63 73 5f | 37 37 39 30 31 38 34 30 |raphics_|77901840|
|00000110| 34 40 62 61 67 67 69 6e | 73 2e 64 61 7a 69 78 63 |4@baggin|s.dazixc|
|00000120| 6f 2e 69 6e 67 72 2e 63 | 6f 6d 3e 0a 46 6f 6c 6c |o.ingr.c|om>.Foll|
|00000130| 6f 77 75 70 2d 54 6f 3a | 20 63 6f 6d 70 2e 67 72 |owup-To:| comp.gr|
|00000140| 61 70 68 69 63 73 2e 61 | 6c 67 6f 72 69 74 68 6d |aphics.a|lgorithm|
|00000150| 73 0a 44 61 74 65 3a 20 | 39 20 4f 63 74 20 31 39 |s.Date: |9 Oct 19|
|00000160| 39 34 20 31 30 3a 30 30 | 3a 30 36 20 47 4d 54 0a |94 10:00|:06 GMT.|
|00000170| 4f 72 67 61 6e 69 7a 61 | 74 69 6f 6e 3a 20 49 6e |Organiza|tion: In|
|00000180| 74 65 72 67 72 61 70 68 | 20 43 6f 72 70 2e 2c 20 |tergraph| Corp., |
|00000190| 42 6f 75 6c 64 65 72 20 | 43 4f 0a 52 65 70 6c 79 |Boulder |CO.Reply|
|000001a0| 2d 54 6f 3a 20 6a 64 73 | 74 6f 6e 65 40 69 6e 67 |-To: jds|tone@ing|
|000001b0| 72 2e 63 6f 6d 0a 4e 4e | 54 50 2d 50 6f 73 74 69 |r.com.NN|TP-Posti|
|000001c0| 6e 67 2d 48 6f 73 74 3a | 20 64 65 73 74 69 6e 2e |ng-Host:| destin.|
|000001d0| 64 61 7a 69 78 63 6f 2e | 69 6e 67 72 2e 63 6f 6d |dazixco.|ingr.com|
|000001e0| 0a 53 75 6d 6d 61 72 79 | 3a 20 54 68 69 73 20 70 |.Summary|: This p|
|000001f0| 6f 73 74 69 6e 67 20 63 | 6f 6e 74 61 69 6e 73 20 |osting c|ontains |
|00000200| 61 20 6c 69 73 74 20 6f | 66 20 46 72 65 71 75 65 |a list o|f Freque|
|00000210| 6e 74 6c 79 20 41 73 6b | 65 64 0a 09 20 51 75 65 |ntly Ask|ed.. Que|
|00000220| 73 74 69 6f 6e 73 20 28 | 61 6e 64 20 74 68 65 69 |stions (|and thei|
|00000230| 72 20 61 6e 73 77 65 72 | 73 29 20 61 62 6f 75 74 |r answer|s) about|
|00000240| 20 63 6f 6d 70 75 74 65 | 72 20 67 72 61 70 68 69 | compute|r graphi|
|00000250| 63 73 0a 09 20 61 6c 67 | 6f 72 69 74 68 6d 73 2e |cs.. alg|orithms.|
|00000260| 20 49 74 20 73 68 6f 75 | 6c 64 20 62 65 20 72 65 | It shou|ld be re|
|00000270| 61 64 20 62 79 20 61 6e | 79 6f 6e 65 20 77 68 6f |ad by an|yone who|
|00000280| 20 77 69 73 68 65 73 20 | 74 6f 0a 09 20 70 6f 73 | wishes |to.. pos|
|00000290| 74 20 74 6f 20 74 68 65 | 20 63 6f 6d 70 2e 67 72 |t to the| comp.gr|
|000002a0| 61 70 68 69 63 73 2e 61 | 6c 67 6f 72 69 74 68 6d |aphics.a|lgorithm|
|000002b0| 73 20 6e 65 77 73 67 72 | 6f 75 70 2e 0a 0a 41 72 |s newsgr|oup...Ar|
|000002c0| 63 68 69 76 65 2d 6e 61 | 6d 65 3a 09 20 20 20 67 |chive-na|me:. g|
|000002d0| 72 61 70 68 69 63 73 2f | 61 6c 67 6f 72 69 74 68 |raphics/|algorith|
|000002e0| 6d 73 2d 66 61 71 0a 56 | 65 72 73 69 6f 6e 3a 20 |ms-faq.V|ersion: |
|000002f0| 20 20 20 20 20 20 20 20 | 20 20 31 2e 31 34 0a 4c | | 1.14.L|
|00000300| 61 73 74 2d 4d 6f 64 69 | 66 69 65 64 3a 20 20 20 |ast-Modi|fied: |
|00000310| 20 20 53 65 70 74 65 6d | 62 65 72 20 32 39 2c 20 | Septem|ber 29, |
|00000320| 31 39 39 34 0a 50 6f 73 | 74 69 6e 67 2d 46 72 65 |1994.Pos|ting-Fre|
|00000330| 71 75 65 6e 63 79 3a 20 | 6d 6f 6e 74 68 6c 79 0a |quency: |monthly.|
|00000340| 0a 0a 0a 57 65 6c 63 6f | 6d 65 20 74 6f 20 74 68 |...Welco|me to th|
|00000350| 65 20 46 41 51 20 66 6f | 72 20 63 6f 6d 70 2e 67 |e FAQ fo|r comp.g|
|00000360| 72 61 70 68 69 63 73 2e | 61 6c 67 6f 72 69 74 68 |raphics.|algorith|
|00000370| 6d 73 21 0a 0a 54 68 61 | 6e 6b 73 20 74 6f 20 61 |ms!..Tha|nks to a|
|00000380| 6c 6c 20 77 68 6f 20 68 | 61 76 65 20 63 6f 6e 74 |ll who h|ave cont|
|00000390| 72 69 62 75 74 65 64 2e | 20 20 43 6f 72 72 65 63 |ributed.| Correc|
|000003a0| 74 69 6f 6e 73 20 61 6e | 64 20 63 6f 6e 74 72 69 |tions an|d contri|
|000003b0| 62 75 74 69 6f 6e 73 0a | 61 6c 77 61 79 73 20 77 |butions.|always w|
|000003c0| 65 6c 63 6f 6d 65 2e 0a | 0a 43 68 61 6e 67 65 64 |elcome..|.Changed|
|000003d0| 20 69 74 65 6d 73 20 61 | 72 65 20 6d 61 72 6b 65 | items a|re marke|
|000003e0| 64 20 77 69 74 68 20 61 | 20 7c 2e 0a 4e 65 77 20 |d with a| |..New |
|000003f0| 69 74 65 6d 73 20 61 72 | 65 20 6d 61 72 6b 65 64 |items ar|e marked|
|00000400| 20 77 69 74 68 20 61 20 | 2b 2e 0a 49 74 65 6d 73 | with a |+..Items|
|00000410| 20 6e 65 65 64 69 6e 67 | 20 69 6e 70 75 74 20 61 | needing| input a|
|00000420| 72 65 20 6d 61 72 6b 65 | 64 20 77 69 74 68 20 61 |re marke|d with a|
|00000430| 20 3f 2e 0a 0a 41 6c 6c | 20 66 74 70 20 20 20 20 | ?...All| ftp |
|00000440| 72 65 66 65 72 65 6e 63 | 65 73 20 61 72 65 20 6f |referenc|es are o|
|00000450| 66 20 74 68 65 20 66 6f | 72 6d 20 66 74 70 3a 2f |f the fo|rm ftp:/|
|00000460| 2f 6e 6f 64 65 2f 70 61 | 74 68 0a 41 6c 6c 20 4d |/node/pa|th.All M|
|00000470| 6f 73 61 69 63 20 72 65 | 66 65 72 65 6e 63 65 73 |osaic re|ferences|
|00000480| 20 61 72 65 20 6f 66 20 | 74 68 65 20 66 6f 72 6d | are of |the form|
|00000490| 20 68 74 74 70 3a 2f 2f | 6e 6f 64 65 2f 70 61 74 | http://|node/pat|
|000004a0| 68 0a 0a 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |h..-----|--------|
|000004b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000004e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 0a 54 61 62 6c 65 20 |--------|-.Table |
|000004f0| 6f 66 20 43 6f 6e 74 65 | 6e 74 73 0a 2d 2d 2d 2d |of Conte|nts.----|
|00000500| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000510| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000520| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000530| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000540| 2d 2d 0a 0a 20 20 20 30 | 29 20 43 68 61 72 74 65 |--.. 0|) Charte|
|00000550| 72 20 6f 66 20 63 6f 6d | 70 2e 67 72 61 70 68 69 |r of com|p.graphi|
|00000560| 63 73 2e 61 6c 67 6f 72 | 69 74 68 6d 73 0a 7c 20 |cs.algor|ithms.| |
|00000570| 20 31 29 20 41 72 65 20 | 74 68 65 20 70 6f 73 74 | 1) Are |the post|
|00000580| 69 6e 67 73 20 74 6f 20 | 63 6f 6d 70 2e 67 72 61 |ings to |comp.gra|
|00000590| 70 68 69 63 73 2e 61 6c | 67 6f 72 69 74 68 6d 73 |phics.al|gorithms|
|000005a0| 20 61 72 63 68 69 76 65 | 64 3f 0a 20 20 20 32 29 | archive|d?. 2)|
|000005b0| 20 57 68 61 74 20 61 72 | 65 20 73 6f 6d 65 20 6d | What ar|e some m|
|000005c0| 75 73 74 20 68 61 76 65 | 20 62 6f 6f 6b 73 20 6f |ust have| books o|
|000005d0| 6e 20 67 72 61 70 68 69 | 63 73 20 61 6c 67 6f 72 |n graphi|cs algor|
|000005e0| 69 74 68 6d 73 3f 0a 20 | 20 20 33 29 20 41 72 65 |ithms?. | 3) Are|
|000005f0| 20 74 68 65 72 65 20 61 | 6e 79 20 6f 6e 6c 69 6e | there a|ny onlin|
|00000600| 65 20 72 65 66 65 72 65 | 6e 63 65 73 3f 0a 20 20 |e refere|nces?. |
|00000610| 20 34 29 20 57 68 65 72 | 65 20 69 73 20 61 6c 6c | 4) Wher|e is all|
|00000620| 20 74 68 65 20 73 6f 75 | 72 63 65 3f 0a 20 20 20 | the sou|rce?. |
|00000630| 35 29 20 48 6f 77 20 64 | 6f 20 49 20 72 6f 74 61 |5) How d|o I rota|
|00000640| 74 65 20 61 20 32 44 20 | 70 6f 69 6e 74 3f 0a 20 |te a 2D |point?. |
|00000650| 20 20 36 29 20 48 6f 77 | 20 64 6f 20 49 20 72 6f | 6) How| do I ro|
|00000660| 74 61 74 65 20 61 20 33 | 44 20 70 6f 69 6e 74 3f |tate a 3|D point?|
|00000670| 0a 20 20 20 37 29 20 48 | 6f 77 20 64 6f 20 49 20 |. 7) H|ow do I |
|00000680| 66 69 6e 64 20 74 68 65 | 20 64 69 73 74 61 6e 63 |find the| distanc|
|00000690| 65 20 66 72 6f 6d 20 61 | 20 70 6f 69 6e 74 20 74 |e from a| point t|
|000006a0| 6f 20 61 20 6c 69 6e 65 | 3f 0a 20 20 20 38 29 20 |o a line|?. 8) |
|000006b0| 48 6f 77 20 64 6f 20 49 | 20 66 69 6e 64 20 69 6e |How do I| find in|
|000006c0| 74 65 72 73 65 63 74 69 | 6f 6e 73 20 6f 66 20 32 |tersecti|ons of 2|
|000006d0| 20 32 44 20 6c 69 6e 65 | 20 73 65 67 6d 65 6e 74 | 2D line| segment|
|000006e0| 73 3f 0a 20 20 20 39 29 | 20 48 6f 77 20 64 6f 20 |s?. 9)| How do |
|000006f0| 49 20 66 69 6e 64 20 74 | 68 65 20 69 6e 74 65 72 |I find t|he inter|
|00000700| 73 65 63 74 69 6f 6e 20 | 6f 66 20 61 20 6c 69 6e |section |of a lin|
|00000710| 65 20 61 6e 64 20 61 20 | 70 6c 61 6e 65 3f 0a 20 |e and a |plane?. |
|00000720| 20 31 30 29 20 48 6f 77 | 20 64 6f 20 49 20 72 6f | 10) How| do I ro|
|00000730| 74 61 74 65 20 61 20 62 | 69 74 6d 61 70 3f 0a 20 |tate a b|itmap?. |
|00000740| 20 31 31 29 20 48 6f 77 | 20 64 6f 20 49 20 64 69 | 11) How| do I di|
|00000750| 73 70 6c 61 79 20 61 20 | 32 34 20 62 69 74 20 69 |splay a |24 bit i|
|00000760| 6d 61 67 65 20 69 6e 20 | 38 20 62 69 74 73 3f 0a |mage in |8 bits?.|
|00000770| 20 20 31 32 29 20 48 6f | 77 20 64 6f 20 49 20 66 | 12) Ho|w do I f|
|00000780| 69 6c 6c 20 74 68 65 20 | 61 72 65 61 20 61 6e 20 |ill the |area an |
|00000790| 61 72 62 69 74 72 61 72 | 79 20 73 68 61 70 65 3f |arbitrar|y shape?|
|000007a0| 0a 20 20 31 33 29 20 48 | 6f 77 20 64 6f 20 49 20 |. 13) H|ow do I |
|000007b0| 66 69 6e 64 20 74 68 65 | 20 27 65 64 67 65 73 27 |find the| 'edges'|
|000007c0| 20 69 6e 20 61 20 62 69 | 74 6d 61 70 3f 0a 3f 20 | in a bi|tmap?.? |
|000007d0| 31 34 29 20 48 6f 77 20 | 64 6f 20 49 20 65 6e 6c |14) How |do I enl|
|000007e0| 61 72 67 65 2f 73 68 61 | 72 70 65 6e 2f 66 75 7a |arge/sha|rpen/fuz|
|000007f0| 7a 20 61 20 62 69 74 6d | 61 70 3f 0a 20 20 31 35 |z a bitm|ap?. 15|
|00000800| 29 20 48 6f 77 20 64 6f | 20 49 20 6d 61 70 20 61 |) How do| I map a|
|00000810| 20 74 65 78 74 75 72 65 | 20 6f 6e 20 74 6f 20 61 | texture| on to a|
|00000820| 20 73 68 61 70 65 3f 0a | 20 20 31 36 29 20 48 6f | shape?.| 16) Ho|
|00000830| 77 20 64 6f 20 49 20 66 | 69 6e 64 20 74 68 65 20 |w do I f|ind the |
|00000840| 61 72 65 61 2f 6f 72 69 | 65 6e 74 61 74 69 6f 6e |area/ori|entation|
|00000850| 20 6f 66 20 61 20 70 6f | 6c 79 67 6f 6e 3f 0a 20 | of a po|lygon?. |
|00000860| 20 31 37 29 20 48 6f 77 | 20 64 6f 20 49 20 66 69 | 17) How| do I fi|
|00000870| 6e 64 20 69 66 20 61 20 | 70 6f 69 6e 74 20 6c 69 |nd if a |point li|
|00000880| 65 73 20 77 69 74 68 69 | 6e 20 61 20 70 6f 6c 79 |es withi|n a poly|
|00000890| 67 6f 6e 3f 0a 3f 20 31 | 38 29 20 48 6f 77 20 64 |gon?.? 1|8) How d|
|000008a0| 6f 20 49 20 66 69 6e 64 | 20 74 68 65 20 69 6e 74 |o I find| the int|
|000008b0| 65 72 73 65 63 74 69 6f | 6e 20 6f 66 20 74 77 6f |ersectio|n of two|
|000008c0| 20 63 6f 6e 76 65 78 20 | 70 6f 6c 79 67 6f 6e 73 | convex |polygons|
|000008d0| 3f 0a 20 20 31 39 29 20 | 48 6f 77 20 64 6f 20 49 |?. 19) |How do I|
|000008e0| 20 64 65 74 65 63 74 20 | 61 20 27 63 6f 72 6e 65 | detect |a 'corne|
|000008f0| 72 27 20 69 6e 20 61 20 | 63 6f 6c 6c 65 63 74 69 |r' in a |collecti|
|00000900| 6f 6e 20 6f 66 20 70 6f | 69 6e 74 73 3f 0a 20 20 |on of po|ints?. |
|00000910| 32 30 29 20 48 6f 77 20 | 64 6f 20 49 20 67 65 6e |20) How |do I gen|
|00000920| 65 72 61 74 65 20 61 20 | 63 69 72 63 6c 65 20 74 |erate a |circle t|
|00000930| 68 72 6f 75 67 68 20 74 | 68 72 65 65 20 70 6f 69 |hrough t|hree poi|
|00000940| 6e 74 73 3f 0a 20 20 32 | 31 29 20 48 6f 77 20 64 |nts?. 2|1) How d|
|00000950| 6f 20 49 20 67 65 6e 65 | 72 61 74 65 20 61 20 62 |o I gene|rate a b|
|00000960| 65 7a 69 65 72 20 63 75 | 72 76 65 20 74 68 61 74 |ezier cu|rve that|
|00000970| 20 69 73 20 70 61 72 61 | 6c 6c 65 6c 20 74 6f 20 | is para|llel to |
|00000980| 61 6e 6f 74 68 65 72 20 | 62 65 7a 69 65 72 3f 0a |another |bezier?.|
|00000990| 20 20 32 32 29 20 48 6f | 77 20 64 6f 20 49 20 73 | 22) Ho|w do I s|
|000009a0| 70 6c 69 74 20 61 20 62 | 65 7a 69 65 72 20 61 74 |plit a b|ezier at|
|000009b0| 20 61 20 73 70 65 63 69 | 66 69 63 20 76 61 6c 75 | a speci|fic valu|
|000009c0| 65 20 66 6f 72 20 74 3f | 0a 20 20 32 33 29 20 48 |e for t?|. 23) H|
|000009d0| 6f 77 20 64 6f 20 49 20 | 66 69 6e 64 20 61 20 74 |ow do I |find a t|
|000009e0| 20 76 61 6c 75 65 20 61 | 74 20 61 20 73 70 65 63 | value a|t a spec|
|000009f0| 69 66 69 63 20 70 6f 69 | 6e 74 20 6f 6e 20 61 20 |ific poi|nt on a |
|00000a00| 62 65 7a 69 65 72 3f 0a | 20 20 32 34 29 20 48 6f |bezier?.| 24) Ho|
|00000a10| 77 20 64 6f 20 49 20 66 | 69 74 20 61 20 62 65 7a |w do I f|it a bez|
|00000a20| 69 65 72 20 63 75 72 76 | 65 20 74 6f 20 61 20 63 |ier curv|e to a c|
|00000a30| 69 72 63 6c 65 3f 0a 20 | 20 32 35 29 20 57 68 61 |ircle?. | 25) Wha|
|00000a40| 74 20 69 73 20 41 52 43 | 42 41 4c 4c 3f 0a 20 20 |t is ARC|BALL?. |
|00000a50| 32 36 29 20 57 68 65 72 | 65 20 63 61 6e 20 49 20 |26) Wher|e can I |
|00000a60| 66 69 6e 64 20 41 52 43 | 42 41 4c 4c 20 73 6f 75 |find ARC|BALL sou|
|00000a70| 72 63 65 3f 0a 20 20 32 | 37 29 20 48 6f 77 20 64 |rce?. 2|7) How d|
|00000a80| 6f 20 49 20 63 6c 69 70 | 20 61 20 70 6f 6c 79 67 |o I clip| a polyg|
|00000a90| 6f 6e 20 61 67 61 69 6e | 73 74 20 61 20 72 65 63 |on again|st a rec|
|00000aa0| 74 61 6e 67 6c 65 3f 0a | 20 20 32 38 29 20 48 6f |tangle?.| 28) Ho|
|00000ab0| 77 20 64 6f 20 49 20 63 | 6c 69 70 20 61 20 70 6f |w do I c|lip a po|
|00000ac0| 6c 79 67 6f 6e 20 61 67 | 61 69 6e 73 74 20 61 6e |lygon ag|ainst an|
|00000ad0| 6f 74 68 65 72 20 70 6f | 6c 79 67 6f 6e 3f 0a 3f |other po|lygon?.?|
|00000ae0| 20 32 39 29 20 57 68 65 | 72 65 20 63 61 6e 20 49 | 29) Whe|re can I|
|00000af0| 20 67 65 74 20 73 6f 75 | 72 63 65 20 66 6f 72 20 | get sou|rce for |
|00000b00| 57 65 69 6c 65 72 2f 41 | 74 68 65 72 74 6f 6e 20 |Weiler/A|therton |
|00000b10| 63 6c 69 70 70 69 6e 67 | 3f 0a 3f 20 33 30 29 20 |clipping|?.? 30) |
|00000b20| 48 6f 77 20 64 6f 20 49 | 20 67 65 6e 65 72 61 74 |How do I| generat|
|00000b30| 65 20 61 20 73 70 6c 69 | 6e 65 20 74 6f 20 61 70 |e a spli|ne to ap|
|00000b40| 70 72 6f 78 69 6d 61 74 | 65 20 28 69 6e 73 65 72 |proximat|e (inser|
|00000b50| 74 20 63 75 72 76 65 20 | 68 65 72 65 29 3f 0a 3f |t curve |here)?.?|
|00000b60| 20 33 31 29 20 57 68 65 | 72 65 20 64 6f 20 49 20 | 31) Whe|re do I |
|00000b70| 67 65 74 20 73 6f 75 72 | 63 65 20 74 6f 20 64 69 |get sour|ce to di|
|00000b80| 73 70 6c 61 79 20 28 72 | 61 73 74 65 72 20 66 6f |splay (r|aster fo|
|00000b90| 6e 74 20 66 6f 72 6d 61 | 74 29 3f 0a 3f 20 33 32 |nt forma|t)?.? 32|
|00000ba0| 29 20 57 68 61 74 20 69 | 73 20 6d 6f 72 70 68 69 |) What i|s morphi|
|00000bb0| 6e 67 2f 68 6f 77 20 69 | 73 20 69 74 20 64 6f 6e |ng/how i|s it don|
|00000bc0| 65 3f 0a 3f 20 33 33 29 | 20 48 6f 77 20 64 6f 20 |e?.? 33)| How do |
|00000bd0| 49 20 64 72 61 77 20 61 | 6e 20 61 6e 74 69 2d 61 |I draw a|n anti-a|
|00000be0| 6c 69 61 73 65 64 20 6c | 69 6e 65 2f 70 6f 6c 79 |liased l|ine/poly|
|00000bf0| 67 6f 6e 2f 65 6c 6c 69 | 70 73 65 3f 0a 20 20 33 |gon/elli|pse?. 3|
|00000c00| 34 29 20 48 6f 77 20 64 | 6f 20 49 20 64 65 74 65 |4) How d|o I dete|
|00000c10| 72 6d 69 6e 65 20 74 68 | 65 20 69 6e 74 65 72 73 |rmine th|e inters|
|00000c20| 65 63 74 69 6f 6e 20 62 | 65 74 77 65 65 6e 20 61 |ection b|etween a|
|00000c30| 20 72 61 79 20 61 6e 64 | 20 61 20 70 6f 6c 79 67 | ray and| a polyg|
|00000c40| 6f 6e 3f 0a 20 20 33 35 | 29 20 48 6f 77 20 64 6f |on?. 35|) How do|
|00000c50| 20 49 20 64 65 74 65 72 | 6d 69 6e 65 20 74 68 65 | I deter|mine the|
|00000c60| 20 69 6e 74 65 72 73 65 | 63 74 69 6f 6e 20 62 65 | interse|ction be|
|00000c70| 74 77 65 65 6e 20 61 20 | 72 61 79 20 61 6e 64 20 |tween a |ray and |
|00000c80| 61 20 73 70 68 65 72 65 | 3f 0a 20 20 33 36 29 20 |a sphere|?. 36) |
|00000c90| 48 6f 77 20 64 6f 20 49 | 20 64 65 74 65 72 6d 69 |How do I| determi|
|00000ca0| 6e 65 20 74 68 65 20 69 | 6e 74 65 72 73 65 63 74 |ne the i|ntersect|
|00000cb0| 69 6f 6e 20 62 65 74 77 | 65 65 6e 20 61 20 72 61 |ion betw|een a ra|
|00000cc0| 79 20 61 6e 64 20 61 20 | 62 65 7a 69 65 72 20 73 |y and a |bezier s|
|00000cd0| 75 72 66 61 63 65 3f 0a | 20 20 33 37 29 20 48 6f |urface?.| 37) Ho|
|00000ce0| 77 20 64 6f 20 49 20 72 | 61 79 20 74 72 61 63 65 |w do I r|ay trace|
|00000cf0| 20 63 61 75 73 74 69 63 | 73 3f 0a 20 20 33 38 29 | caustic|s?. 38)|
|00000d00| 20 48 6f 77 20 64 6f 20 | 49 20 71 75 69 63 6b 6c | How do |I quickl|
|00000d10| 79 20 64 72 61 77 20 61 | 20 66 69 6c 6c 65 64 20 |y draw a| filled |
|00000d20| 74 72 69 61 6e 67 6c 65 | 3f 0a 20 20 33 39 29 20 |triangle|?. 39) |
|00000d30| 57 68 65 72 65 20 63 61 | 6e 20 49 20 67 65 74 20 |Where ca|n I get |
|00000d40| 73 6f 75 72 63 65 20 66 | 6f 72 20 56 6f 72 6f 6e |source f|or Voron|
|00000d50| 6f 69 2f 44 65 6c 61 75 | 6e 61 79 20 74 72 69 61 |oi/Delau|nay tria|
|00000d60| 6e 67 75 6c 61 74 69 6f | 6e 3f 0a 20 20 34 30 29 |ngulatio|n?. 40)|
|00000d70| 20 57 68 65 72 65 20 64 | 6f 20 49 20 67 65 74 20 | Where d|o I get |
|00000d80| 73 6f 75 72 63 65 20 66 | 6f 72 20 63 6f 6e 76 65 |source f|or conve|
|00000d90| 78 20 68 75 6c 6c 3f 0a | 20 20 34 31 29 20 57 68 |x hull?.| 41) Wh|
|00000da0| 61 74 20 69 73 20 74 68 | 65 20 6d 61 72 63 68 69 |at is th|e marchi|
|00000db0| 6e 67 20 63 75 62 65 73 | 20 61 6c 67 6f 72 69 74 |ng cubes| algorit|
|00000dc0| 68 6d 3f 0a 3f 20 34 32 | 29 20 57 68 61 74 20 69 |hm?.? 42|) What i|
|00000dd0| 73 20 74 68 65 20 73 74 | 61 74 75 73 20 6f 66 20 |s the st|atus of |
|00000de0| 74 68 65 20 70 61 74 65 | 6e 74 20 6f 6e 20 74 68 |the pate|nt on th|
|00000df0| 65 20 22 6d 61 72 63 68 | 69 6e 67 20 63 75 62 65 |e "march|ing cube|
|00000e00| 73 22 20 61 6c 67 6f 72 | 69 74 68 6d 3f 0a 20 20 |s" algor|ithm?. |
|00000e10| 34 33 29 20 48 6f 77 20 | 64 6f 20 49 20 64 6f 20 |43) How |do I do |
|00000e20| 61 20 68 69 64 64 65 6e | 20 73 75 72 66 61 63 65 |a hidden| surface|
|00000e30| 20 74 65 73 74 20 28 62 | 61 63 6b 66 61 63 65 20 | test (b|ackface |
|00000e40| 63 75 6c 6c 69 6e 67 29 | 20 77 69 74 68 20 33 64 |culling)| with 3d|
|00000e50| 20 70 6f 69 6e 74 73 3f | 0a 20 20 34 34 29 20 48 | points?|. 44) H|
|00000e60| 6f 77 20 64 6f 20 49 20 | 64 6f 20 61 20 68 69 64 |ow do I |do a hid|
|00000e70| 64 65 6e 20 73 75 72 66 | 61 63 65 20 74 65 73 74 |den surf|ace test|
|00000e80| 20 28 62 61 63 6b 66 61 | 63 65 20 63 75 6c 6c 69 | (backfa|ce culli|
|00000e90| 6e 67 29 20 77 69 74 68 | 20 32 64 20 70 6f 69 6e |ng) with| 2d poin|
|00000ea0| 74 73 3f 0a 20 20 34 35 | 29 20 57 68 65 72 65 20 |ts?. 45|) Where |
|00000eb0| 63 61 6e 20 49 20 66 69 | 6e 64 20 67 72 61 70 68 |can I fi|nd graph|
|00000ec0| 20 6c 61 79 6f 75 74 20 | 61 6c 67 6f 72 69 74 68 | layout |algorith|
|00000ed0| 6d 73 3f 0a 3f 20 34 36 | 29 20 57 68 65 72 65 20 |ms?.? 46|) Where |
|00000ee0| 63 61 6e 20 49 20 66 69 | 6e 64 20 61 6c 67 6f 72 |can I fi|nd algor|
|00000ef0| 69 74 68 6d 73 20 66 6f | 72 20 32 44 20 63 6f 6c |ithms fo|r 2D col|
|00000f00| 6c 69 73 69 6f 6e 20 64 | 65 74 65 63 74 69 6f 6e |lision d|etection|
|00000f10| 3f 0a 20 20 34 37 29 20 | 57 68 65 72 65 20 63 61 |?. 47) |Where ca|
|00000f20| 6e 20 49 20 66 69 6e 64 | 20 61 6c 67 6f 72 69 74 |n I find| algorit|
|00000f30| 68 6d 73 20 66 6f 72 20 | 33 44 20 63 6f 6c 6c 69 |hms for |3D colli|
|00000f40| 73 69 6f 6e 20 64 65 74 | 65 63 74 69 6f 6e 3f 0a |sion det|ection?.|
|00000f50| 20 20 34 38 29 20 33 44 | 20 4e 6f 69 73 65 20 66 | 48) 3D| Noise f|
|00000f60| 75 6e 63 74 69 6f 6e 73 | 20 61 6e 64 20 74 75 72 |unctions| and tur|
|00000f70| 62 75 6c 65 6e 63 65 20 | 69 6e 20 53 6f 6c 69 64 |bulence |in Solid|
|00000f80| 20 74 65 78 74 75 72 69 | 6e 67 2e 0a 20 20 34 39 | texturi|ng.. 49|
|00000f90| 29 20 48 6f 77 20 64 6f | 20 49 20 70 65 72 66 6f |) How do| I perfo|
|00000fa0| 72 6d 20 62 61 73 69 63 | 20 76 69 65 77 69 6e 67 |rm basic| viewing|
|00000fb0| 20 69 6e 20 33 64 3f 0a | 3f 20 35 30 29 20 48 6f | in 3d?.|? 50) Ho|
|00000fc0| 77 20 63 61 6e 20 79 6f | 75 20 63 6f 6e 74 72 69 |w can yo|u contri|
|00000fd0| 62 75 74 65 20 74 6f 20 | 74 68 69 73 20 46 41 51 |bute to |this FAQ|
|00000fe0| 3f 0a 20 20 35 31 29 20 | 43 6f 6e 74 72 69 62 75 |?. 51) |Contribu|
|00000ff0| 74 6f 72 73 2e 20 20 57 | 68 6f 20 6d 61 64 65 20 |tors. W|ho made |
|00001000| 74 68 69 73 20 61 6c 6c | 20 70 6f 73 73 69 62 6c |this all| possibl|
|00001010| 65 2e 0a 0a 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |e...----|--------|
|00001020| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001030| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001040| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001050| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0a 0a 53 75 62 6a |--------|--..Subj|
|00001060| 65 63 74 3a 20 30 29 20 | 43 68 61 72 74 65 72 20 |ect: 0) |Charter |
|00001070| 6f 66 20 63 6f 6d 70 2e | 67 72 61 70 68 69 63 73 |of comp.|graphics|
|00001080| 2e 61 6c 67 6f 72 69 74 | 68 6d 73 0a 0a 20 20 20 |.algorit|hms.. |
|00001090| 20 43 6f 6d 70 2e 67 72 | 61 70 68 69 63 73 2e 61 | Comp.gr|aphics.a|
|000010a0| 6c 67 6f 72 69 74 68 6d | 73 20 69 73 20 61 6e 20 |lgorithm|s is an |
|000010b0| 75 6e 6d 6f 64 65 72 61 | 74 65 64 20 6e 65 77 73 |unmodera|ted news|
|000010c0| 67 72 6f 75 70 20 69 6e | 74 65 6e 64 65 64 0a 20 |group in|tended. |
|000010d0| 20 20 20 61 73 20 61 20 | 66 6f 72 75 6d 20 66 6f | as a |forum fo|
|000010e0| 72 20 74 68 65 20 64 69 | 73 63 75 73 73 69 6f 6e |r the di|scussion|
|000010f0| 20 6f 66 20 74 68 65 20 | 61 6c 67 6f 72 69 74 68 | of the |algorith|
|00001100| 6d 73 20 75 73 65 64 20 | 69 6e 20 74 68 65 0a 20 |ms used |in the. |
|00001110| 20 20 20 70 72 6f 63 65 | 73 73 20 6f 66 20 67 65 | proce|ss of ge|
|00001120| 6e 65 72 61 74 69 6e 67 | 20 63 6f 6d 70 75 74 65 |nerating| compute|
|00001130| 72 20 67 72 61 70 68 69 | 63 73 2e 20 20 54 68 65 |r graphi|cs. The|
|00001140| 73 65 20 61 6c 67 6f 72 | 69 74 68 6d 73 20 6d 61 |se algor|ithms ma|
|00001150| 79 0a 20 20 20 20 62 65 | 20 72 65 63 65 6e 74 6c |y. be| recentl|
|00001160| 79 20 70 72 6f 70 6f 73 | 65 64 20 69 6e 20 70 75 |y propos|ed in pu|
|00001170| 62 6c 69 73 68 65 64 20 | 6a 6f 75 72 6e 61 6c 73 |blished |journals|
|00001180| 20 6f 72 20 70 61 70 65 | 72 73 2c 20 6f 6c 64 20 | or pape|rs, old |
|00001190| 6f 72 0a 20 20 20 20 70 | 72 65 76 69 6f 75 73 6c |or. p|reviousl|
|000011a0| 79 20 6b 6e 6f 77 6e 20 | 61 6c 67 6f 72 69 74 68 |y known |algorith|
|000011b0| 6d 73 2c 20 6f 72 20 68 | 61 63 6b 73 20 75 73 65 |ms, or h|acks use|
|000011c0| 64 20 69 6e 63 69 64 65 | 6e 74 61 6c 20 74 6f 20 |d incide|ntal to |
|000011d0| 74 68 65 0a 20 20 20 20 | 70 72 6f 63 65 73 73 20 |the. |process |
|000011e0| 6f 66 20 63 6f 6d 70 75 | 74 65 72 20 67 72 61 70 |of compu|ter grap|
|000011f0| 68 69 63 73 2e 20 20 54 | 68 65 20 73 63 6f 70 65 |hics. T|he scope|
|00001200| 20 6f 66 20 74 68 65 73 | 65 20 61 6c 67 6f 72 69 | of thes|e algori|
|00001210| 74 68 6d 73 0a 20 20 20 | 20 6d 61 79 20 72 61 6e |thms. | may ran|
|00001220| 67 65 20 66 72 6f 6d 20 | 61 6e 20 65 66 66 69 63 |ge from |an effic|
|00001230| 69 65 6e 74 20 77 61 79 | 20 74 6f 20 6d 75 6c 74 |ient way| to mult|
|00001240| 69 70 6c 79 20 6d 61 74 | 72 69 63 65 73 2c 20 61 |iply mat|rices, a|
|00001250| 6c 6c 20 74 68 65 0a 20 | 20 20 20 77 61 79 20 74 |ll the. | way t|
|00001260| 6f 20 61 20 67 6c 6f 62 | 61 6c 20 69 6c 6c 75 6d |o a glob|al illum|
|00001270| 69 6e 61 74 69 6f 6e 20 | 6d 65 74 68 6f 64 20 69 |ination |method i|
|00001280| 6e 63 6f 72 70 6f 72 61 | 74 69 6e 67 20 72 61 79 |ncorpora|ting ray|
|00001290| 20 74 72 61 63 69 6e 67 | 2c 0a 20 20 20 20 72 61 | tracing|,. ra|
|000012a0| 64 69 6f 73 69 74 79 2c | 20 69 6e 66 69 6e 69 74 |diosity,| infinit|
|000012b0| 65 20 73 70 65 63 74 72 | 75 6d 20 6d 6f 64 65 6c |e spectr|um model|
|000012c0| 69 6e 67 2c 20 61 6e 64 | 20 70 65 72 68 61 70 73 |ing, and| perhaps|
|000012d0| 20 65 76 65 6e 0a 20 20 | 20 20 6d 69 72 72 6f 72 | even. | mirror|
|000012e0| 65 64 20 62 61 6c 6c 73 | 20 61 6e 64 20 6c 69 6d |ed balls| and lim|
|000012f0| 65 20 6a 65 6c 6c 6f 2e | 0a 20 0a 20 20 20 20 49 |e jello.|. . I|
|00001300| 74 20 69 73 20 68 6f 70 | 65 64 20 74 68 61 74 20 |t is hop|ed that |
|00001310| 74 68 69 73 20 67 72 6f | 75 70 20 77 69 6c 6c 20 |this gro|up will |
|00001320| 73 65 72 76 65 20 61 73 | 20 61 20 66 6f 72 75 6d |serve as| a forum|
|00001330| 20 66 6f 72 20 70 72 6f | 67 72 61 6d 6d 65 72 73 | for pro|grammers|
|00001340| 0a 20 20 20 20 61 6e 64 | 20 72 65 73 65 61 72 63 |. and| researc|
|00001350| 68 65 72 73 20 74 6f 20 | 65 78 63 68 61 6e 67 65 |hers to |exchange|
|00001360| 20 69 64 65 61 73 20 61 | 6e 64 20 61 73 6b 20 71 | ideas a|nd ask q|
|00001370| 75 65 73 74 69 6f 6e 73 | 20 6f 6e 20 72 65 63 65 |uestions| on rece|
|00001380| 6e 74 0a 20 20 20 20 70 | 61 70 65 72 73 20 6f 72 |nt. p|apers or|
|00001390| 20 63 75 72 72 65 6e 74 | 20 72 65 73 65 61 72 63 | current| researc|
|000013a0| 68 20 72 65 6c 61 74 65 | 64 20 74 6f 20 63 6f 6d |h relate|d to com|
|000013b0| 70 75 74 65 72 20 67 72 | 61 70 68 69 63 73 2e 0a |puter gr|aphics..|
|000013c0| 0a 20 20 20 20 63 6f 6d | 70 2e 67 72 61 70 68 69 |. com|p.graphi|
|000013d0| 63 73 2e 61 6c 67 6f 72 | 69 74 68 6d 73 20 69 73 |cs.algor|ithms is|
|000013e0| 20 6e 6f 74 3a 0a 0a 20 | 20 20 20 20 2d 20 66 6f | not:.. | - fo|
|000013f0| 72 20 72 65 71 75 65 73 | 74 73 20 66 6f 72 20 67 |r reques|ts for g|
|00001400| 69 66 73 2c 20 6f 72 20 | 6f 74 68 65 72 20 70 69 |ifs, or |other pi|
|00001410| 63 74 75 72 65 73 0a 20 | 20 20 20 20 2d 20 66 6f |ctures. | - fo|
|00001420| 72 20 72 65 71 75 65 73 | 74 73 20 66 6f 72 20 69 |r reques|ts for i|
|00001430| 6d 61 67 65 20 74 72 61 | 6e 73 6c 61 74 6f 72 20 |mage tra|nslator |
|00001440| 73 6f 66 74 77 61 72 65 | 20 28 69 2e 65 2e 20 67 |software| (i.e. g|
|00001450| 69 66 20 3c 2d 2d 3e 20 | 6a 70 67 29 0a 0a 2d 2d |if <--> |jpg)..--|
|00001460| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001470| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001480| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001490| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000014a0| 2d 2d 2d 2d 0a 0a 53 75 | 62 6a 65 63 74 3a 20 31 |----..Su|bject: 1|
|000014b0| 29 20 41 72 65 20 74 68 | 65 20 70 6f 73 74 69 6e |) Are th|e postin|
|000014c0| 67 73 20 74 6f 20 63 6f | 6d 70 2e 67 72 61 70 68 |gs to co|mp.graph|
|000014d0| 69 63 73 2e 61 6c 67 6f | 72 69 74 68 6d 73 20 61 |ics.algo|rithms a|
|000014e0| 72 63 68 69 76 65 64 3f | 0a 0a 7c 20 20 20 59 65 |rchived?|..| Ye|
|000014f0| 73 2e 20 20 54 68 65 20 | 22 6f 66 66 69 63 69 61 |s. The |"officia|
|00001500| 6c 22 20 61 72 63 68 69 | 76 65 20 69 73 20 73 74 |l" archi|ve is st|
|00001510| 6f 72 65 64 20 61 74 3a | 0a 7c 0a 7c 20 20 20 20 |ored at:|.|.| |
|00001520| 20 68 74 74 70 3a 2f 2f | 77 77 77 2e 63 69 73 2e | http://|www.cis.|
|00001530| 6f 68 69 6f 2d 73 74 61 | 74 65 2f 68 79 70 65 72 |ohio-sta|te/hyper|
|00001540| 74 65 78 74 2f 66 61 71 | 2f 75 73 65 6e 65 74 2f |text/faq|/usenet/|
|00001550| 67 72 61 70 68 69 63 73 | 2f 61 6c 67 6f 72 69 74 |graphics|/algorit|
|00001560| 68 6d 73 2d 66 61 71 2f | 66 61 71 2e 68 74 6d 6c |hms-faq/|faq.html|
|00001570| 0a 7c 20 20 20 20 20 66 | 74 70 3a 2f 2f 72 74 66 |.| f|tp://rtf|
|00001580| 6d 2e 6d 69 74 2e 65 64 | 75 2f 70 75 62 2f 75 73 |m.mit.ed|u/pub/us|
|00001590| 65 6e 65 74 2d 62 79 2d | 67 72 6f 75 70 2f 6e 65 |enet-by-|group/ne|
|000015a0| 77 73 2e 61 6e 73 77 65 | 72 73 2f 67 72 61 70 68 |ws.answe|rs/graph|
|000015b0| 69 63 73 2f 61 6c 67 6f | 72 69 74 68 6d 73 2d 66 |ics/algo|rithms-f|
|000015c0| 61 71 0a 7c 0a 7c 20 20 | 20 41 6c 73 6f 20 61 76 |aq.|.| | Also av|
|000015d0| 61 69 6c 61 62 6c 65 20 | 61 74 3a 0a 7c 0a 7c 20 |ailable |at:.|.| |
|000015e0| 20 20 20 20 66 74 70 3a | 2f 2f 77 75 61 72 63 68 | ftp:|//wuarch|
|000015f0| 69 76 65 2e 77 75 73 74 | 6c 2e 65 64 75 2f 67 72 |ive.wust|l.edu/gr|
|00001600| 61 70 68 69 63 73 2f 67 | 72 61 70 68 69 63 73 2f |aphics/g|raphics/|
|00001610| 6d 61 69 6c 2d 6c 69 73 | 74 73 2f 63 6f 6d 70 2e |mail-lis|ts/comp.|
|00001620| 67 72 61 70 68 69 63 73 | 2e 61 6c 67 6f 72 69 74 |graphics|.algorit|
|00001630| 68 6d 73 0a 0a 20 20 20 | 20 49 74 20 69 73 20 61 |hms.. | It is a|
|00001640| 72 63 68 69 76 65 64 20 | 69 6e 20 74 68 65 20 73 |rchived |in the s|
|00001650| 61 6d 65 20 6d 61 6e 6e | 65 72 20 74 68 61 74 20 |ame mann|er that |
|00001660| 61 6c 6c 20 6f 74 68 65 | 72 20 6e 65 77 73 67 72 |all othe|r newsgr|
|00001670| 6f 75 70 73 20 61 72 65 | 0a 20 20 20 20 62 65 69 |oups are|. bei|
|00001680| 6e 67 20 61 72 63 68 69 | 76 65 64 20 74 68 65 72 |ng archi|ved ther|
|00001690| 65 2c 20 6e 61 6d 65 6c | 79 20 74 68 65 72 65 20 |e, namel|y there |
|000016a0| 69 73 20 61 6e 20 49 6e | 64 65 78 20 66 69 6c 65 |is an In|dex file|
|000016b0| 20 77 69 74 68 20 61 6c | 6c 20 74 68 65 0a 20 20 | with al|l the. |
|000016c0| 20 20 73 75 62 6a 65 63 | 74 73 2c 20 61 6e 64 20 | subjec|ts, and |
|000016d0| 61 6c 6c 20 74 68 65 20 | 61 72 74 69 63 6c 65 73 |all the |articles|
|000016e0| 20 61 72 65 20 62 65 69 | 6e 67 20 6b 65 70 74 20 | are bei|ng kept |
|000016f0| 69 6e 20 61 20 68 69 65 | 72 61 72 63 68 79 20 62 |in a hie|rarchy b|
|00001700| 61 73 65 64 0a 20 20 20 | 20 6f 6e 20 74 68 65 20 |ased. | on the |
|00001710| 79 65 61 72 20 61 6e 64 | 20 6d 6f 6e 74 68 20 74 |year and| month t|
|00001720| 68 65 79 20 61 72 65 20 | 70 6f 73 74 65 64 2e 0a |hey are |posted..|
|00001730| 0a 7c 20 20 20 46 59 49 | 2c 20 61 6c 6c 20 75 73 |.| FYI|, all us|
|00001740| 65 6e 65 74 20 46 41 51 | 27 73 20 61 72 65 20 61 |enet FAQ|'s are a|
|00001750| 76 61 69 6c 61 62 6c 65 | 20 77 69 74 68 20 4d 6f |vailable| with Mo|
|00001760| 73 61 69 63 20 76 69 61 | 0a 7c 0a 7c 20 20 20 68 |saic via|.|.| h|
|00001770| 74 74 70 3a 2f 2f 77 77 | 77 2e 63 69 73 2e 6f 68 |ttp://ww|w.cis.oh|
|00001780| 69 6f 2d 73 74 61 74 65 | 2f 68 79 70 65 72 74 65 |io-state|/hyperte|
|00001790| 78 74 2f 66 61 71 2f 75 | 73 65 6e 65 74 2f 74 6f |xt/faq/u|senet/to|
|000017a0| 70 2e 68 74 6d 6c 0a 0a | 0a 2d 2d 2d 2d 2d 2d 2d |p.html..|.-------|
|000017b0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000017c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000017d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000017e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 0a |--------|-------.|
|000017f0| 0a 53 75 62 6a 65 63 74 | 3a 20 32 29 20 57 68 61 |.Subject|: 2) Wha|
|00001800| 74 20 61 72 65 20 73 6f | 6d 65 20 6d 75 73 74 20 |t are so|me must |
|00001810| 68 61 76 65 20 62 6f 6f | 6b 73 20 6f 6e 20 67 72 |have boo|ks on gr|
|00001820| 61 70 68 69 63 73 20 61 | 6c 67 6f 72 69 74 68 6d |aphics a|lgorithm|
|00001830| 73 3f 0a 0a 20 20 20 20 | 54 68 65 20 6b 65 79 77 |s?.. |The keyw|
|00001840| 6f 72 64 73 20 69 6e 20 | 62 72 61 63 6b 65 74 73 |ords in |brackets|
|00001850| 20 61 72 65 20 75 73 65 | 64 20 74 6f 20 72 65 66 | are use|d to ref|
|00001860| 65 72 20 74 6f 20 74 68 | 65 20 62 6f 6f 6b 73 20 |er to th|e books |
|00001870| 69 6e 20 6c 61 74 65 72 | 0a 20 20 20 20 71 75 65 |in later|. que|
|00001880| 73 74 69 6f 6e 73 2e 20 | 20 54 68 65 79 20 67 65 |stions. | They ge|
|00001890| 6e 65 72 61 6c 6c 79 20 | 72 65 66 65 72 20 74 6f |nerally |refer to|
|000018a0| 20 74 68 65 20 66 69 72 | 73 74 20 61 75 74 68 6f | the fir|st autho|
|000018b0| 72 20 65 78 63 65 70 74 | 20 77 68 65 72 65 0a 20 |r except| where. |
|000018c0| 20 20 20 69 74 20 69 73 | 20 6e 65 63 65 73 73 61 | it is| necessa|
|000018d0| 72 79 20 74 6f 20 72 65 | 73 6f 6c 76 65 20 61 6d |ry to re|solve am|
|000018e0| 62 69 67 75 69 74 79 20 | 6f 72 20 69 6e 20 74 68 |biguity |or in th|
|000018f0| 65 20 63 61 73 65 20 6f | 66 20 74 68 65 20 47 65 |e case o|f the Ge|
|00001900| 6d 73 2e 0a 0a 0a 20 20 | 20 20 42 61 73 69 63 20 |ms.... | Basic |
|00001910| 63 6f 6d 70 75 74 65 72 | 20 67 72 61 70 68 69 63 |computer| graphic|
|00001920| 73 2c 20 72 65 6e 64 65 | 72 69 6e 67 20 61 6c 67 |s, rende|ring alg|
|00001930| 6f 72 69 74 68 6d 73 2c | 0a 20 20 20 20 2d 2d 2d |orithms,|. ---|
|00001940| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001950| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00001960| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 0a 0a 20 20 20 |--------|---.. |
|00001970| 20 5b 46 6f 6c 65 79 5d | 0a 20 20 20 20 43 6f 6d | [Foley]|. Com|
|00001980| 70 75 74 65 72 20 47 72 | 61 70 68 69 63 73 3a 20 |puter Gr|aphics: |
|00001990| 50 72 69 6e 63 69 70 6c | 65 73 20 61 6e 64 20 50 |Principl|es and P|
|000019a0| 72 61 63 74 69 63 65 20 | 28 32 6e 64 20 45 64 2e |ractice |(2nd Ed.|
|000019b0| 29 2c 0a 20 20 20 20 4a | 2e 44 2e 20 46 6f 6c 65 |),. J|.D. Fole|
|000019c0| 79 2c 20 41 2e 20 76 61 | 6e 20 44 61 6d 2c 20 53 |y, A. va|n Dam, S|
|000019d0| 2e 4b 2e 20 46 65 69 6e | 65 72 2c 20 4a 2e 46 2e |.K. Fein|er, J.F.|
|000019e0| 20 48 75 67 68 65 73 2c | 20 41 64 64 69 73 6f 6e | Hughes,| Addison|
|000019f0| 2d 57 65 73 6c 65 79 0a | 20 20 20 20 31 39 39 30 |-Wesley.| 1990|
|00001a00| 2c 20 49 53 42 4e 20 30 | 2d 32 30 31 2d 31 32 31 |, ISBN 0|-201-121|
|00001a10| 31 30 2d 37 0a 0a 20 20 | 20 20 5b 52 6f 67 65 72 |10-7.. | [Roger|
|00001a20| 73 3a 50 72 6f 63 65 64 | 75 72 61 6c 5d 0a 20 20 |s:Proced|ural]. |
|00001a30| 20 20 50 72 6f 63 65 64 | 75 72 61 6c 20 45 6c 65 | Proced|ural Ele|
|00001a40| 6d 65 6e 74 73 20 66 6f | 72 20 43 6f 6d 70 75 74 |ments fo|r Comput|
|00001a50| 65 72 20 47 72 61 70 68 | 69 63 73 2c 0a 20 20 20 |er Graph|ics,. |
|00001a60| 20 44 61 76 69 64 20 46 | 2e 20 52 6f 67 65 72 73 | David F|. Rogers|
|00001a70| 2c 20 4d 63 47 72 61 77 | 20 48 69 6c 6c 20 31 39 |, McGraw| Hill 19|
|00001a80| 38 35 2c 20 49 53 42 4e | 20 30 2d 30 37 2d 30 35 |85, ISBN| 0-07-05|
|00001a90| 33 35 33 34 2d 35 0a 0a | 20 20 20 20 5b 52 6f 67 |3534-5..| [Rog|
|00001aa0| 65 72 73 3a 4d 61 74 68 | 65 6d 61 74 69 63 61 6c |ers:Math|ematical|
|00001ab0| 5d 0a 20 20 20 20 4d 61 | 74 68 65 6d 61 74 69 63 |]. Ma|thematic|
|00001ac0| 61 6c 20 45 6c 65 6d 65 | 6e 74 73 20 66 6f 72 20 |al Eleme|nts for |
|00001ad0| 43 6f 6d 70 75 74 65 72 | 20 47 72 61 70 68 69 63 |Computer| Graphic|
|00001ae0| 73 20 32 6e 64 20 45 64 | 2e 2c 0a 20 20 20 20 44 |s 2nd Ed|.,. D|
|00001af0| 61 76 69 64 20 46 2e 20 | 52 6f 67 65 72 73 20 61 |avid F. |Rogers a|
|00001b00| 6e 64 20 4a 2e 20 41 6c | 61 6e 20 41 64 61 6d 73 |nd J. Al|an Adams|
|00001b10| 2c 20 4d 63 47 72 61 77 | 20 48 69 6c 6c 20 31 39 |, McGraw| Hill 19|
|00001b20| 39 30 2c 20 49 53 42 4e | 0a 20 20 20 20 30 2d 30 |90, ISBN|. 0-0|
|00001b30| 37 2d 30 35 33 35 33 30 | 2d 32 0a 0a 20 20 20 20 |7-053530|-2.. |
|00001b40| 5b 57 61 74 74 3a 33 44 | 5d 0a 20 20 20 20 5f 33 |[Watt:3D|]. _3|
|00001b50| 44 20 43 6f 6d 70 75 74 | 65 72 20 47 72 61 70 68 |D Comput|er Graph|
|00001b60| 69 63 73 2c 20 32 6e 64 | 20 45 64 69 74 69 6f 6e |ics, 2nd| Edition|
|00001b70| 5f 2c 0a 20 20 20 20 41 | 6c 61 6e 20 57 61 74 74 |_,. A|lan Watt|
|00001b80| 2c 20 41 64 64 69 73 6f | 6e 2d 57 65 73 6c 65 79 |, Addiso|n-Wesley|
|00001b90| 20 31 39 39 33 2c 20 49 | 53 42 4e 20 30 2d 32 30 | 1993, I|SBN 0-20|
|00001ba0| 31 2d 36 33 31 38 36 2d | 35 0a 0a 20 20 20 20 5b |1-63186-|5.. [|
|00001bb0| 47 6c 61 73 73 6e 65 72 | 3a 52 61 79 54 72 61 63 |Glassner|:RayTrac|
|00001bc0| 69 6e 67 5d 0a 20 20 20 | 20 41 6e 20 49 6e 74 72 |ing]. | An Intr|
|00001bd0| 6f 64 75 63 74 69 6f 6e | 20 74 6f 20 52 61 79 20 |oduction| to Ray |
|00001be0| 54 72 61 63 69 6e 67 2c | 0a 20 20 20 20 41 6e 64 |Tracing,|. And|
|00001bf0| 72 65 77 20 47 6c 61 73 | 73 6e 65 72 20 28 65 64 |rew Glas|sner (ed|
|00001c00| 2e 29 2c 20 41 63 61 64 | 65 6d 69 63 20 50 72 65 |.), Acad|emic Pre|
|00001c10| 73 73 20 31 39 38 39 2c | 20 49 53 42 4e 20 30 2d |ss 1989,| ISBN 0-|
|00001c20| 31 32 2d 32 38 36 31 36 | 30 2d 34 0a 0a 20 20 20 |12-28616|0-4.. |
|00001c30| 20 5b 47 65 6d 73 20 49 | 5d 0a 20 20 20 20 47 72 | [Gems I|]. Gr|
|00001c40| 61 70 68 69 63 73 20 47 | 65 6d 73 2c 0a 20 20 20 |aphics G|ems,. |
|00001c50| 20 41 6e 64 72 65 77 20 | 47 6c 61 73 73 6e 65 72 | Andrew |Glassner|
|00001c60| 20 28 65 64 2e 29 2c 20 | 41 63 61 64 65 6d 69 63 | (ed.), |Academic|
|00001c70| 20 50 72 65 73 73 20 31 | 39 39 30 2c 20 49 53 42 | Press 1|990, ISB|
|00001c80| 4e 20 30 2d 31 32 2d 32 | 38 36 31 36 35 2d 35 0a |N 0-12-2|86165-5.|
|00001c90| 0a 20 20 20 20 5b 47 65 | 6d 73 20 49 49 5d 0a 20 |. [Ge|ms II]. |
|00001ca0| 20 20 20 47 72 61 70 68 | 69 63 73 20 47 65 6d 73 | Graph|ics Gems|
|00001cb0| 20 49 49 2c 0a 20 20 20 | 20 4a 61 6d 65 73 20 41 | II,. | James A|
|00001cc0| 72 76 6f 20 28 65 64 2e | 29 2c 20 41 63 61 64 65 |rvo (ed.|), Acade|
|00001cd0| 6d 69 63 20 50 72 65 73 | 73 20 31 39 39 31 2c 20 |mic Pres|s 1991, |
|00001ce0| 49 53 42 4e 20 30 2d 31 | 32 2d 36 34 34 38 30 2d |ISBN 0-1|2-64480-|
|00001cf0| 30 0a 0a 20 20 20 20 5b | 47 65 6d 73 20 49 49 49 |0.. [|Gems III|
|00001d00| 5d 0a 20 20 20 20 47 72 | 61 70 68 69 63 73 20 47 |]. Gr|aphics G|
|00001d10| 65 6d 73 20 49 49 49 2c | 0a 20 20 20 20 44 61 76 |ems III,|. Dav|
|00001d20| 69 64 20 4b 69 72 6b 20 | 28 65 64 2e 29 2c 20 41 |id Kirk |(ed.), A|
|00001d30| 63 61 64 65 6d 69 63 20 | 50 72 65 73 73 20 31 39 |cademic |Press 19|
|00001d40| 39 32 2c 20 49 53 42 4e | 20 30 2d 31 32 2d 34 30 |92, ISBN| 0-12-40|
|00001d50| 39 36 37 30 2d 30 20 28 | 77 69 74 68 0a 20 20 20 |9670-0 (|with. |
|00001d60| 20 49 42 4d 20 64 69 73 | 6b 29 20 6f 72 20 30 2d | IBM dis|k) or 0-|
|00001d70| 31 32 2d 34 30 39 36 37 | 31 2d 39 20 28 77 69 74 |12-40967|1-9 (wit|
|00001d80| 68 20 4d 61 63 20 64 69 | 73 6b 29 0a 0a 20 20 20 |h Mac di|sk).. |
|00001d90| 20 5b 47 65 6d 73 20 49 | 56 5d 0a 20 20 20 20 47 | [Gems I|V]. G|
|00001da0| 72 61 70 68 69 63 73 20 | 47 65 6d 73 20 49 56 2c |raphics |Gems IV,|
|00001db0| 0a 20 20 20 20 50 61 75 | 6c 20 53 2e 20 48 65 63 |. Pau|l S. Hec|
|00001dc0| 6b 62 65 72 74 20 28 65 | 64 2e 29 2c 20 41 63 61 |kbert (e|d.), Aca|
|00001dd0| 64 65 6d 69 63 20 50 72 | 65 73 73 20 31 39 39 34 |demic Pr|ess 1994|
|00001de0| 2c 20 49 53 42 4e 20 30 | 2d 31 32 2d 33 33 36 31 |, ISBN 0|-12-3361|
|00001df0| 35 35 2d 39 0a 20 20 20 | 20 28 77 69 74 68 20 49 |55-9. | (with I|
|00001e00| 42 4d 20 64 69 73 6b 29 | 20 6f 72 20 30 2d 31 32 |BM disk)| or 0-12|
|00001e10| 2d 33 33 36 31 35 36 2d | 37 20 28 77 69 74 68 20 |-336156-|7 (with |
|00001e20| 4d 61 63 20 64 69 73 6b | 29 0a 0a 20 20 20 20 5b |Mac disk|).. [|
|00001e30| 57 61 74 74 3a 41 6e 69 | 6d 61 74 69 6f 6e 5d 0a |Watt:Ani|mation].|
|00001e40| 20 20 20 20 41 64 76 61 | 6e 63 65 64 20 41 6e 69 | Adva|nced Ani|
|00001e50| 6d 61 74 69 6f 6e 20 61 | 6e 64 20 52 65 6e 64 65 |mation a|nd Rende|
|00001e60| 72 69 6e 67 20 54 65 63 | 68 6e 69 71 75 65 73 2c |ring Tec|hniques,|
|00001e70| 0a 20 20 20 20 41 6c 61 | 6e 20 57 61 74 74 2c 20 |. Ala|n Watt, |
|00001e80| 4d 61 72 6b 20 57 61 74 | 74 2c 20 41 64 64 69 73 |Mark Wat|t, Addis|
|00001e90| 6f 6e 2d 57 65 73 6c 65 | 79 20 31 39 39 32 2c 20 |on-Wesle|y 1992, |
|00001ea0| 49 53 42 4e 20 30 2d 32 | 30 31 2d 35 34 34 31 32 |ISBN 0-2|01-54412|
|00001eb0| 2d 31 0a 0a 20 20 20 20 | 5b 42 61 72 74 65 6c 73 |-1.. |[Bartels|
|00001ec0| 5d 0a 20 20 20 20 41 6e | 20 49 6e 74 72 6f 64 75 |]. An| Introdu|
|00001ed0| 63 74 69 6f 6e 20 74 6f | 20 53 70 6c 69 6e 65 73 |ction to| Splines|
|00001ee0| 20 66 6f 72 20 55 73 65 | 20 69 6e 20 43 6f 6d 70 | for Use| in Comp|
|00001ef0| 75 74 65 72 20 47 72 61 | 70 68 69 63 73 20 61 6e |uter Gra|phics an|
|00001f00| 64 0a 20 20 20 20 20 20 | 20 20 47 65 6f 6d 65 74 |d. | Geomet|
|00001f10| 72 69 63 20 4d 6f 64 65 | 6c 69 6e 67 2c 0a 20 20 |ric Mode|ling,. |
|00001f20| 20 20 52 69 63 68 61 72 | 64 20 48 2e 20 42 61 72 | Richar|d H. Bar|
|00001f30| 74 65 6c 73 2c 20 4a 6f | 68 6e 20 43 2e 20 42 65 |tels, Jo|hn C. Be|
|00001f40| 61 74 74 79 2c 20 42 72 | 69 61 6e 20 41 2e 20 42 |atty, Br|ian A. B|
|00001f50| 61 72 73 6b 79 2c 20 31 | 39 38 37 2c 20 49 53 42 |arsky, 1|987, ISB|
|00001f60| 4e 0a 20 20 20 20 30 2d | 39 33 34 36 31 33 2d 32 |N. 0-|934613-2|
|00001f70| 37 2d 33 0a 0a 20 20 20 | 20 5b 46 61 72 69 6e 5d |7-3.. | [Farin]|
|00001f80| 0a 20 20 20 20 43 75 72 | 76 65 73 20 61 6e 64 20 |. Cur|ves and |
|00001f90| 53 75 72 66 61 63 65 73 | 20 66 6f 72 20 43 6f 6d |Surfaces| for Com|
|00001fa0| 70 75 74 65 72 20 41 69 | 64 65 64 20 47 65 6f 6d |puter Ai|ded Geom|
|00001fb0| 65 74 72 69 63 20 44 65 | 73 69 67 6e 3a 0a 20 20 |etric De|sign:. |
|00001fc0| 20 20 41 20 50 72 61 63 | 74 69 63 61 6c 20 47 75 | A Prac|tical Gu|
|00001fd0| 69 64 65 2c 20 33 72 64 | 20 45 64 69 74 69 6f 6e |ide, 3rd| Edition|
|00001fe0| 2c 20 47 65 72 61 6c 64 | 20 45 2e 20 46 61 72 69 |, Gerald| E. Fari|
|00001ff0| 6e 2c 20 41 63 61 64 65 | 6d 69 63 20 50 72 65 73 |n, Acade|mic Pres|
|00002000| 73 0a 20 20 20 20 31 39 | 39 33 2e 20 49 53 42 4e |s. 19|93. ISBN|
|00002010| 20 30 2d 31 32 2d 32 34 | 39 30 35 32 2d 35 0a 0a | 0-12-24|9052-5..|
|00002020| 20 20 20 20 5b 50 72 75 | 73 69 6e 6b 69 65 77 69 | [Pru|sinkiewi|
|00002030| 63 7a 5d 0a 20 20 20 20 | 54 68 65 20 41 6c 67 6f |cz]. |The Algo|
|00002040| 72 69 74 68 6d 69 63 20 | 42 65 61 75 74 79 20 6f |rithmic |Beauty o|
|00002050| 66 20 50 6c 61 6e 74 73 | 2c 0a 20 20 20 20 50 72 |f Plants|,. Pr|
|00002060| 7a 65 6d 79 73 6c 61 77 | 20 57 2e 20 50 72 75 73 |zemyslaw| W. Prus|
|00002070| 69 6e 6b 69 65 77 69 63 | 7a 2c 20 41 72 69 73 74 |inkiewic|z, Arist|
|00002080| 69 64 20 4c 69 6e 64 65 | 6e 6d 61 79 65 72 2c 20 |id Linde|nmayer, |
|00002090| 53 70 72 69 6e 67 65 72 | 2d 56 65 72 6c 61 67 2c |Springer|-Verlag,|
|000020a0| 0a 20 20 20 20 31 39 39 | 30 2c 20 49 53 42 4e 20 |. 199|0, ISBN |
|000020b0| 30 2d 33 38 37 2d 39 37 | 32 39 37 2d 38 2c 20 49 |0-387-97|297-8, I|
|000020c0| 53 42 4e 20 33 2d 35 34 | 30 2d 39 37 32 39 37 2d |SBN 3-54|0-97297-|
|000020d0| 38 0a 0a 20 20 20 20 5b | 4f 6c 69 76 65 72 5d 0a |8.. [|Oliver].|
|000020e0| 20 20 20 20 54 72 69 63 | 6b 73 20 6f 66 20 74 68 | Tric|ks of th|
|000020f0| 65 20 47 72 61 70 68 69 | 63 73 20 47 75 72 75 73 |e Graphi|cs Gurus|
|00002100| 2c 0a 20 20 20 20 44 69 | 63 6b 20 4f 6c 69 76 65 |,. Di|ck Olive|
|00002110| 72 2c 20 65 74 20 61 6c | 2e 20 28 32 29 20 33 2e |r, et al|. (2) 3.|
|00002120| 35 20 50 43 20 64 69 73 | 6b 73 20 69 6e 63 6c 75 |5 PC dis|ks inclu|
|00002130| 64 65 64 2c 20 24 33 39 | 2e 39 35 20 53 41 4d 53 |ded, $39|.95 SAMS|
|00002140| 20 50 75 62 6c 69 73 68 | 69 6e 67 0a 0a 20 20 20 | Publish|ing.. |
|00002150| 20 5b 48 65 61 72 6e 5d | 0a 20 20 20 20 49 6e 74 | [Hearn]|. Int|
|00002160| 72 6f 64 75 63 74 69 6f | 6e 20 74 6f 20 63 6f 6d |roductio|n to com|
|00002170| 70 75 74 65 72 20 67 72 | 61 70 68 69 63 73 2c 0a |puter gr|aphics,.|
|00002180| 20 20 20 20 48 65 61 72 | 6e 20 26 20 42 61 6b 65 | Hear|n & Bake|
|00002190| 72 0a 0a 0a 20 20 20 20 | 46 6f 72 20 69 6d 61 67 |r... |For imag|
|000021a0| 65 20 70 72 6f 63 65 73 | 73 69 6e 67 2c 0a 20 20 |e proces|sing,. |
|000021b0| 20 20 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | ------|--------|
|000021c0| 2d 2d 2d 2d 2d 2d 2d 0a | 0a 20 20 20 20 5b 42 61 |-------.|. [Ba|
|000021d0| 72 6e 73 6c 65 79 5d 0a | 20 20 20 20 46 72 61 63 |rnsley].| Frac|
|000021e0| 74 61 6c 20 49 6d 61 67 | 65 20 43 6f 6d 70 72 65 |tal Imag|e Compre|
|000021f0| 73 73 69 6f 6e 2c 0a 20 | 20 20 20 4d 69 63 68 61 |ssion,. | Micha|
|00002200| 65 6c 20 46 2e 20 42 61 | 72 6e 73 6c 65 79 20 61 |el F. Ba|rnsley a|
|00002210| 6e 64 20 4c 79 6d 61 6e | 20 50 2e 20 48 75 72 64 |nd Lyman| P. Hurd|
|00002220| 2c 20 41 4b 20 50 65 74 | 65 72 73 2c 20 4c 74 64 |, AK Pet|ers, Ltd|
|00002230| 2c 20 31 39 39 33 20 49 | 53 42 4e 0a 20 20 20 20 |, 1993 I|SBN. |
|00002240| 31 2d 35 36 38 38 31 2d | 30 30 30 2d 38 0a 0a 20 |1-56881-|000-8.. |
|00002250| 20 20 20 5b 4a 61 69 6e | 5d 0a 20 20 20 20 46 75 | [Jain|]. Fu|
|00002260| 6e 64 61 6d 65 6e 74 61 | 6c 73 20 6f 66 20 49 6d |ndamenta|ls of Im|
|00002270| 61 67 65 20 50 72 6f 63 | 65 73 73 69 6e 67 2c 0a |age Proc|essing,.|
|00002280| 20 20 20 20 41 6e 69 6c | 20 4b 2e 20 4a 61 69 6e | Anil| K. Jain|
|00002290| 2c 20 50 72 65 6e 74 69 | 63 65 2d 48 61 6c 6c 20 |, Prenti|ce-Hall |
|000022a0| 31 39 38 39 2c 20 49 53 | 42 4e 20 30 2d 31 33 2d |1989, IS|BN 0-13-|
|000022b0| 33 33 36 31 36 35 2d 39 | 0a 0a 20 20 20 20 5b 43 |336165-9|.. [C|
|000022c0| 61 73 74 6c 65 6d 61 6e | 5d 0a 20 20 20 20 44 69 |astleman|]. Di|
|000022d0| 67 69 74 61 6c 20 49 6d | 61 67 65 20 50 72 6f 63 |gital Im|age Proc|
|000022e0| 65 73 73 69 6e 67 2c 0a | 20 20 20 20 4b 65 6e 6e |essing,.| Kenn|
|000022f0| 65 74 68 20 52 2e 20 43 | 61 73 74 6c 65 6d 61 6e |eth R. C|astleman|
|00002300| 2c 20 50 72 65 6e 74 69 | 63 65 2d 48 61 6c 6c 20 |, Prenti|ce-Hall |
|00002310| 31 39 37 39 2c 20 49 53 | 42 4e 20 30 2d 31 33 2d |1979, IS|BN 0-13-|
|00002320| 32 31 32 33 36 35 2d 37 | 0a 0a 20 20 20 20 5b 50 |212365-7|.. [P|
|00002330| 72 61 74 74 5d 0a 20 20 | 20 20 44 69 67 69 74 61 |ratt]. | Digita|
|00002340| 6c 20 49 6d 61 67 65 20 | 50 72 6f 63 65 73 73 69 |l Image |Processi|
|00002350| 6e 67 2c 20 53 65 63 6f | 6e 64 20 45 64 69 74 69 |ng, Seco|nd Editi|
|00002360| 6f 6e 2c 0a 20 20 20 20 | 57 69 6c 6c 69 61 6d 20 |on,. |William |
|00002370| 4b 2e 20 50 72 61 74 74 | 2c 20 57 69 6c 65 79 2d |K. Pratt|, Wiley-|
|00002380| 49 6e 74 65 72 73 63 69 | 65 6e 63 65 20 31 39 39 |Intersci|ence 199|
|00002390| 31 2c 20 49 53 42 4e 20 | 30 2d 34 37 31 2d 38 35 |1, ISBN |0-471-85|
|000023a0| 37 36 36 2d 31 0a 0a 20 | 20 20 20 5b 47 6f 6e 7a |766-1.. | [Gonz|
|000023b0| 61 6c 65 7a 5d 0a 20 20 | 20 20 44 69 67 69 74 61 |alez]. | Digita|
|000023c0| 6c 20 49 6d 61 67 65 20 | 50 72 6f 63 65 73 73 69 |l Image |Processi|
|000023d0| 6e 67 20 28 32 6e 64 20 | 45 64 2e 29 2c 0a 20 20 |ng (2nd |Ed.),. |
|000023e0| 20 20 52 61 66 61 65 6c | 20 43 2e 20 47 6f 6e 7a | Rafael| C. Gonz|
|000023f0| 61 6c 65 7a 2c 20 50 61 | 75 6c 20 57 69 6e 74 7a |alez, Pa|ul Wintz|
|00002400| 2c 20 41 64 64 69 73 6f | 6e 2d 57 65 73 6c 65 79 |, Addiso|n-Wesley|
|00002410| 20 31 39 38 37 2c 20 49 | 53 42 4e 0a 20 20 20 20 | 1987, I|SBN. |
|00002420| 30 2d 32 30 31 2d 31 31 | 30 32 36 2d 31 0a 0a 20 |0-201-11|026-1.. |
|00002430| 20 20 20 5b 52 75 73 73 | 5d 0a 20 20 20 20 54 68 | [Russ|]. Th|
|00002440| 65 20 49 6d 61 67 65 20 | 50 72 6f 63 65 73 73 69 |e Image |Processi|
|00002450| 6e 67 20 48 61 6e 64 62 | 6f 6f 6b 2c 0a 20 20 20 |ng Handb|ook,. |
|00002460| 20 4a 6f 68 6e 20 43 2e | 20 52 75 73 73 2c 20 43 | John C.| Russ, C|
|00002470| 52 43 20 50 72 65 73 73 | 20 31 39 39 32 2c 20 49 |RC Press| 1992, I|
|00002480| 53 42 4e 20 30 2d 38 34 | 39 33 2d 34 32 33 33 2d |SBN 0-84|93-4233-|
|00002490| 33 0a 0a 20 20 20 20 5b | 57 6f 6c 62 65 72 67 5d |3.. [|Wolberg]|
|000024a0| 0a 20 20 20 20 44 69 67 | 69 74 61 6c 20 49 6d 61 |. Dig|ital Ima|
|000024b0| 67 65 20 57 61 72 70 69 | 6e 67 2c 0a 20 20 20 20 |ge Warpi|ng,. |
|000024c0| 47 65 6f 72 67 65 20 57 | 6f 6c 62 65 72 67 2c 20 |George W|olberg, |
|000024d0| 49 45 45 45 20 43 6f 6d | 70 75 74 65 72 20 53 6f |IEEE Com|puter So|
|000024e0| 63 69 65 74 79 20 50 72 | 65 73 73 20 4d 6f 6e 6f |ciety Pr|ess Mono|
|000024f0| 67 72 61 70 68 20 31 39 | 39 30 2c 20 49 53 42 4e |graph 19|90, ISBN|
|00002500| 0a 20 20 20 20 30 2d 38 | 31 38 36 2d 38 39 34 34 |. 0-8|186-8944|
|00002510| 2d 37 0a 0a 0a 20 20 20 | 20 43 6f 6d 70 75 74 61 |-7... | Computa|
|00002520| 74 69 6f 6e 61 6c 20 67 | 65 6f 6d 65 74 72 79 2c |tional g|eometry,|
|00002530| 0a 20 20 20 20 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |. ---|--------|
|00002540| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 0a 0a 20 20 20 |--------|---.. |
|00002550| 20 5b 42 6f 77 79 65 72 | 5d 0a 20 20 20 20 41 20 | [Bowyer|]. A |
|00002560| 50 72 6f 67 72 61 6d 6d | 65 72 27 73 20 47 65 6f |Programm|er's Geo|
|00002570| 6d 65 74 72 79 2c 0a 20 | 20 20 20 41 64 72 69 61 |metry,. | Adria|
|00002580| 6e 20 42 6f 77 79 65 72 | 2c 20 4a 6f 68 6e 20 57 |n Bowyer|, John W|
|00002590| 6f 6f 64 77 61 72 6b 2c | 20 42 75 74 74 65 72 77 |oodwark,| Butterw|
|000025a0| 6f 72 74 68 73 20 31 39 | 38 33 2c 20 49 53 42 4e |orths 19|83, ISBN|
|000025b0| 0a 20 20 20 20 30 2d 34 | 30 38 2d 30 31 32 34 32 |. 0-4|08-01242|
|000025c0| 2d 30 20 50 62 6b 0a 0a | 20 20 20 20 5b 4f 27 20 |-0 Pbk..| [O' |
|000025d0| 52 6f 75 72 6b 65 5d 0a | 20 20 20 20 43 6f 6d 70 |Rourke].| Comp|
|000025e0| 75 74 61 74 69 6f 6e 61 | 6c 20 47 65 6f 6d 65 74 |utationa|l Geomet|
|000025f0| 72 79 20 69 6e 20 43 2c | 0a 20 20 20 20 4a 6f 73 |ry in C,|. Jos|
|00002600| 65 70 68 20 4f 27 52 6f | 75 72 6b 65 2c 20 43 61 |eph O'Ro|urke, Ca|
|00002610| 6d 62 72 69 64 67 65 20 | 55 6e 69 76 65 72 73 69 |mbridge |Universi|
|00002620| 74 79 20 50 72 65 73 73 | 20 31 39 39 34 2c 20 49 |ty Press| 1994, I|
|00002630| 53 42 4e 0a 20 20 20 20 | 30 2d 35 32 31 2d 34 34 |SBN. |0-521-44|
|00002640| 35 39 32 2d 32 20 50 62 | 6b 2c 20 49 53 42 4e 20 |592-2 Pb|k, ISBN |
|00002650| 30 2d 35 32 31 2d 34 34 | 30 33 34 2d 33 20 48 64 |0-521-44|034-3 Hd|
|00002660| 62 6b 0a 0a 20 20 20 20 | 5b 4d 6f 72 74 65 6e 73 |bk.. |[Mortens|
|00002670| 6f 6e 5d 0a 20 20 20 20 | 47 65 6f 6d 65 74 72 69 |on]. |Geometri|
|00002680| 63 20 4d 6f 64 65 6c 69 | 6e 67 2c 0a 20 20 20 20 |c Modeli|ng,. |
|00002690| 4d 69 63 68 61 65 6c 20 | 45 2e 20 4d 6f 72 74 65 |Michael |E. Morte|
|000026a0| 6e 73 6f 6e 2c 20 57 69 | 6c 65 79 20 31 39 38 35 |nson, Wi|ley 1985|
|000026b0| 2c 20 49 53 42 4e 20 30 | 2d 34 37 31 2d 38 38 32 |, ISBN 0|-471-882|
|000026c0| 37 39 2d 38 0a 0a 20 20 | 20 20 5b 50 72 65 70 61 |79-8.. | [Prepa|
|000026d0| 72 61 74 61 5d 0a 20 20 | 20 20 43 6f 6d 70 75 74 |rata]. | Comput|
|000026e0| 61 74 69 6f 6e 61 6c 20 | 47 65 6f 6d 65 74 72 79 |ational |Geometry|
|000026f0| 3a 20 41 6e 20 49 6e 74 | 72 6f 64 75 63 74 69 6f |: An Int|roductio|
|00002700| 6e 2c 0a 20 20 20 20 46 | 72 61 6e 63 6f 20 50 2e |n,. F|ranco P.|
|00002710| 20 50 72 65 70 61 72 61 | 74 61 2c 20 4d 69 63 68 | Prepara|ta, Mich|
|00002720| 61 65 6c 20 49 61 6e 20 | 53 68 61 6d 6f 73 2c 20 |ael Ian |Shamos, |
|00002730| 53 70 72 69 6e 67 65 72 | 2d 56 65 72 6c 61 67 20 |Springer|-Verlag |
|00002740| 31 39 38 35 2c 0a 20 20 | 20 20 49 53 42 4e 20 30 |1985,. | ISBN 0|
|00002750| 2d 33 38 37 2d 39 36 31 | 33 31 2d 33 0a 0a 0a 2d |-387-961|31-3...-|
|00002760| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002770| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002780| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002790| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000027a0| 2d 2d 2d 2d 2d 0a 0a 53 | 75 62 6a 65 63 74 3a 20 |-----..S|ubject: |
|000027b0| 33 29 20 41 72 65 20 74 | 68 65 72 65 20 61 6e 79 |3) Are t|here any|
|000027c0| 20 6f 6e 6c 69 6e 65 20 | 72 65 66 65 72 65 6e 63 | online |referenc|
|000027d0| 65 73 3f 0a 0a 20 20 20 | 20 54 68 65 20 63 6f 6d |es?.. | The com|
|000027e0| 70 75 74 61 74 69 6f 6e | 61 6c 20 67 65 6f 6d 65 |putation|al geome|
|000027f0| 74 72 79 20 63 6f 6d 6d | 75 6e 69 74 79 20 6d 61 |try comm|unity ma|
|00002800| 69 6e 74 61 69 6e 73 20 | 69 74 73 20 6f 77 6e 0a |intains |its own.|
|00002810| 20 20 20 20 62 69 62 6c | 69 6f 67 72 61 70 68 79 | bibl|iography|
|00002820| 20 6f 66 20 70 75 62 6c | 69 63 61 74 69 6f 6e 73 | of publ|ications|
|00002830| 20 69 6e 20 6f 72 20 63 | 6c 6f 73 65 6c 79 20 72 | in or c|losely r|
|00002840| 65 6c 61 74 65 64 20 74 | 6f 20 74 68 61 74 0a 20 |elated t|o that. |
|00002850| 20 20 20 73 75 62 6a 65 | 63 74 2e 20 20 45 76 65 | subje|ct. Eve|
|00002860| 72 79 20 66 6f 75 72 20 | 6d 6f 6e 74 68 73 2c 20 |ry four |months, |
|00002870| 61 64 64 69 74 69 6f 6e | 73 20 61 6e 64 20 63 6f |addition|s and co|
|00002880| 72 72 65 63 74 69 6f 6e | 73 20 61 72 65 0a 20 20 |rrection|s are. |
|00002890| 20 20 73 6f 6c 69 63 69 | 74 65 64 20 66 72 6f 6d | solici|ted from|
|000028a0| 20 75 73 65 72 73 2c 20 | 61 66 74 65 72 20 77 68 | users, |after wh|
|000028b0| 69 63 68 20 74 68 65 20 | 64 61 74 61 62 61 73 65 |ich the |database|
|000028c0| 20 69 73 20 75 70 64 61 | 74 65 64 20 61 6e 64 0a | is upda|ted and.|
|000028d0| 20 20 20 20 72 65 6c 65 | 61 73 65 64 20 61 6e 65 | rele|ased ane|
|000028e0| 77 2e 20 20 41 73 20 6f | 66 20 53 65 70 74 65 6d |w. As o|f Septem|
|000028f0| 62 65 72 20 31 39 39 33 | 2c 20 69 74 20 63 6f 6e |ber 1993|, it con|
|00002900| 74 61 69 6e 65 64 20 35 | 33 35 36 20 62 69 62 2d |tained 5|356 bib-|
|00002910| 74 65 78 0a 20 20 20 20 | 65 6e 74 72 69 65 73 2e |tex. |entries.|
|00002920| 20 20 49 74 20 63 61 6e | 20 62 65 20 72 65 74 72 | It can| be retr|
|00002930| 69 65 76 65 64 20 66 72 | 6f 6d 0a 20 0a 20 20 20 |ieved fr|om. . |
|00002940| 20 66 74 70 3a 2f 2f 63 | 73 2e 75 73 61 73 6b 2e | ftp://c|s.usask.|
|00002950| 63 61 2f 70 75 62 2f 67 | 65 6f 6d 65 74 72 79 2f |ca/pub/g|eometry/|
|00002960| 67 65 6f 6d 62 69 62 2e | 74 61 72 2e 5a 20 2d 20 |geombib.|tar.Z - |
|00002970| 62 69 62 6c 69 6f 67 72 | 61 70 68 79 20 70 72 6f |bibliogr|aphy pro|
|00002980| 70 65 72 0a 20 0a 20 20 | 20 20 66 74 70 3a 2f 2f |per. . | ftp://|
|00002990| 63 73 2e 75 73 61 73 6b | 2e 63 61 2f 70 75 62 2f |cs.usask|.ca/pub/|
|000029a0| 67 65 6f 6d 65 74 72 79 | 2f 67 65 6f 6d 2e 70 73 |geometry|/geom.ps|
|000029b0| 2e 5a 20 20 20 20 20 2d | 20 50 6f 73 74 53 63 72 |.Z -| PostScr|
|000029c0| 69 70 74 20 66 6f 72 6d | 61 74 0a 20 0a 20 20 20 |ipt form|at. . |
|000029d0| 20 66 74 70 3a 2f 2f 63 | 73 2e 75 73 61 73 6b 2e | ftp://c|s.usask.|
|000029e0| 63 61 2f 70 75 62 2f 67 | 65 6f 6d 65 74 72 79 2f |ca/pub/g|eometry/|
|000029f0| 6f 2d 63 67 63 31 39 2e | 70 73 2e 5a 09 20 2d 20 |o-cgc19.|ps.Z. - |
|00002a00| 6f 76 65 72 76 69 65 77 | 20 70 75 62 6c 69 73 68 |overview| publish|
|00002a10| 65 64 0a 20 20 20 20 20 | 20 20 20 69 6e 20 27 39 |ed. | in '9|
|00002a20| 33 20 69 6e 20 53 49 47 | 41 43 54 20 4e 65 77 73 |3 in SIG|ACT News|
|00002a30| 20 61 6e 64 20 74 68 65 | 20 49 6e 74 65 72 6e 61 | and the| Interna|
|00002a40| 74 2e 20 4a 2e 20 43 6f | 6d 70 75 74 2e 20 20 47 |t. J. Co|mput. G|
|00002a50| 65 6f 6d 2e 20 41 70 70 | 6c 2e 0a 20 0a 20 20 20 |eom. App|l.. . |
|00002a60| 20 66 74 70 3a 2f 2f 63 | 73 2e 75 73 61 73 6b 2e | ftp://c|s.usask.|
|00002a70| 63 61 2f 70 75 62 2f 67 | 65 6f 6d 65 74 72 79 2f |ca/pub/g|eometry/|
|00002a80| 66 74 70 2d 68 69 6e 74 | 73 20 20 20 20 20 2d 20 |ftp-hint|s - |
|00002a90| 64 65 74 61 69 6c 65 64 | 20 72 65 74 72 69 65 76 |detailed| retriev|
|00002aa0| 61 6c 20 69 6e 66 6f 0a | 20 0a 20 20 20 20 41 6e |al info.| . An|
|00002ab0| 6e 6f 75 6e 63 69 6e 67 | 20 74 68 65 20 41 43 4d |nouncing| the ACM|
|00002ac0| 20 53 49 47 47 52 41 50 | 48 20 4f 6e 6c 69 6e 65 | SIGGRAP|H Online|
|00002ad0| 20 42 69 62 6c 69 6f 67 | 72 61 70 68 79 20 50 72 | Bibliog|raphy Pr|
|00002ae0| 6f 6a 65 63 74 2c 20 62 | 79 0a 20 20 20 20 53 74 |oject, b|y. St|
|00002af0| 65 70 68 65 6e 20 53 70 | 65 6e 63 65 72 20 28 62 |ephen Sp|encer (b|
|00002b00| 69 62 6c 69 6f 40 73 69 | 67 67 72 61 70 68 2e 6f |iblio@si|ggraph.o|
|00002b10| 72 67 29 0a 0a 20 20 20 | 20 54 68 65 20 64 61 74 |rg).. | The dat|
|00002b20| 61 62 61 73 65 20 69 73 | 20 61 76 61 69 6c 61 62 |abase is| availab|
|00002b30| 6c 65 20 66 6f 72 20 61 | 6e 6f 6e 79 6d 6f 75 73 |le for a|nonymous|
|00002b40| 20 46 54 50 20 66 72 6f | 6d 20 74 68 65 0a 20 20 | FTP fro|m the. |
|00002b50| 20 20 66 74 70 3a 2f 2f | 73 69 67 67 72 61 70 68 | ftp://|siggraph|
|00002b60| 2e 6f 72 67 2f 70 75 62 | 6c 69 63 61 74 69 6f 6e |.org/pub|lication|
|00002b70| 73 2f 62 69 62 6c 69 6f | 67 72 61 70 68 79 20 64 |s/biblio|graphy d|
|00002b80| 69 72 65 63 74 6f 72 79 | 2e 20 20 50 6c 65 61 73 |irectory|. Pleas|
|00002b90| 65 0a 20 20 20 20 64 6f | 77 6e 6c 6f 61 64 20 61 |e. do|wnload a|
|00002ba0| 6e 64 20 65 78 61 6d 69 | 6e 65 20 74 68 65 20 66 |nd exami|ne the f|
|00002bb0| 69 6c 65 20 52 45 41 44 | 5f 4d 45 20 69 6e 20 74 |ile READ|_ME in t|
|00002bc0| 68 61 74 20 64 69 72 65 | 63 74 6f 72 79 20 66 6f |hat dire|ctory fo|
|00002bd0| 72 20 6d 6f 72 65 0a 20 | 20 20 20 73 70 65 63 69 |r more. | speci|
|00002be0| 66 69 63 20 69 6e 66 6f | 72 6d 61 74 69 6f 6e 20 |fic info|rmation |
|00002bf0| 63 6f 6e 63 65 72 6e 69 | 6e 67 20 74 68 65 20 64 |concerni|ng the d|
|00002c00| 61 74 61 62 61 73 65 2e | 0a 0a 20 20 20 20 27 6e |atabase.|.. 'n|
|00002c10| 65 74 6c 69 62 27 20 69 | 73 20 61 20 75 73 65 66 |etlib' i|s a usef|
|00002c20| 75 6c 20 73 6f 75 72 63 | 65 20 66 6f 72 20 61 6c |ul sourc|e for al|
|00002c30| 67 6f 72 69 74 68 6d 73 | 2c 20 6d 65 6d 62 65 72 |gorithms|, member|
|00002c40| 20 69 6e 71 75 69 72 69 | 65 73 20 66 6f 72 0a 20 | inquiri|es for. |
|00002c50| 20 20 20 53 49 41 4d 2c | 20 61 6e 64 20 62 69 62 | SIAM,| and bib|
|00002c60| 6c 69 6f 67 72 61 70 68 | 69 63 20 73 65 61 72 63 |liograph|ic searc|
|00002c70| 68 65 73 2e 20 20 46 6f | 72 20 69 6e 66 6f 72 6d |hes. Fo|r inform|
|00002c80| 61 74 69 6f 6e 2c 20 73 | 65 6e 64 20 6d 61 69 6c |ation, s|end mail|
|00002c90| 20 74 6f 0a 20 20 20 20 | 6e 65 74 6c 69 62 40 6f | to. |netlib@o|
|00002ca0| 72 6e 6c 2e 67 6f 76 2c | 20 77 69 74 68 20 22 73 |rnl.gov,| with "s|
|00002cb0| 65 6e 64 20 69 6e 64 65 | 78 22 20 69 6e 20 74 68 |end inde|x" in th|
|00002cc0| 65 20 62 6f 64 79 20 6f | 66 20 74 68 65 20 6d 61 |e body o|f the ma|
|00002cd0| 69 6c 0a 20 20 20 20 6d | 65 73 73 61 67 65 2e 0a |il. m|essage..|
|00002ce0| 20 0a 20 20 20 20 59 6f | 75 20 63 61 6e 20 61 6c | . Yo|u can al|
|00002cf0| 73 6f 20 66 69 6e 64 20 | 66 72 65 65 20 73 6f 75 |so find |free sou|
|00002d00| 72 63 65 73 20 66 6f 72 | 20 6e 75 6d 65 72 69 63 |rces for| numeric|
|00002d10| 61 6c 20 63 6f 6d 70 75 | 74 61 74 69 6f 6e 20 69 |al compu|tation i|
|00002d20| 6e 20 43 20 76 69 61 0a | 20 20 20 20 66 74 70 3a |n C via.| ftp:|
|00002d30| 2f 2f 75 73 63 2e 65 64 | 75 2f 70 75 62 2f 43 2d |//usc.ed|u/pub/C-|
|00002d40| 6e 75 6d 61 6e 61 6c 2e | 20 20 49 6e 20 70 61 72 |numanal.| In par|
|00002d50| 74 69 63 75 6c 61 72 2c | 20 67 72 61 62 0a 20 20 |ticular,| grab. |
|00002d60| 20 20 6e 75 6d 63 6f 6d | 70 2d 66 72 65 65 2d 63 | numcom|p-free-c|
|00002d70| 2e 67 7a 20 69 6e 20 74 | 68 61 74 20 64 69 72 65 |.gz in t|hat dire|
|00002d80| 63 74 6f 72 79 2e 20 0a | 20 0a 20 20 20 20 43 68 |ctory. .| . Ch|
|00002d90| 65 63 6b 20 6f 75 74 20 | 4e 69 63 6b 20 46 6f 74 |eck out |Nick Fot|
|00002da0| 69 73 27 73 20 63 6f 6d | 70 75 74 65 72 20 67 72 |is's com|puter gr|
|00002db0| 61 70 68 69 63 73 20 72 | 65 73 6f 75 72 63 65 73 |aphics r|esources|
|00002dc0| 20 46 41 51 20 2d 2d 20 | 69 74 27 73 0a 20 20 20 | FAQ -- |it's. |
|00002dd0| 20 70 61 63 6b 65 64 20 | 77 69 74 68 20 70 6f 69 | packed |with poi|
|00002de0| 6e 74 65 72 73 20 74 6f | 20 61 6c 6c 20 73 6f 72 |nters to| all sor|
|00002df0| 74 73 20 6f 66 20 67 72 | 65 61 74 20 63 6f 6d 70 |ts of gr|eat comp|
|00002e00| 75 74 65 72 20 67 72 61 | 70 68 69 63 73 0a 20 20 |uter gra|phics. |
|00002e10| 20 20 73 74 75 66 66 2e | 20 20 54 68 69 73 20 46 | stuff.| This F|
|00002e20| 41 51 20 69 73 20 70 6f | 73 74 65 64 20 62 69 77 |AQ is po|sted biw|
|00002e30| 65 65 6b 6c 79 20 74 6f | 20 63 6f 6d 70 2e 67 72 |eekly to| comp.gr|
|00002e40| 61 70 68 69 63 73 2e 0a | 0a 0a 2d 2d 2d 2d 2d 2d |aphics..|..------|
|00002e50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002e60| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002e70| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002e80| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002e90| 0a 0a 53 75 62 6a 65 63 | 74 3a 20 34 29 20 57 68 |..Subjec|t: 4) Wh|
|00002ea0| 65 72 65 20 69 73 20 61 | 6c 6c 20 74 68 65 20 73 |ere is a|ll the s|
|00002eb0| 6f 75 72 63 65 3f 0a 0a | 20 20 20 20 47 72 61 70 |ource?..| Grap|
|00002ec0| 68 69 63 73 20 47 65 6d | 73 20 73 6f 75 72 63 65 |hics Gem|s source|
|00002ed0| 20 63 6f 64 65 2e 0a 20 | 20 20 20 66 74 70 3a 2f | code.. | ftp:/|
|00002ee0| 2f 70 72 69 6e 63 65 74 | 6f 6e 2e 65 64 75 3a 70 |/princet|on.edu:p|
|00002ef0| 75 62 2f 47 72 61 70 68 | 69 63 73 2f 47 72 61 70 |ub/Graph|ics/Grap|
|00002f00| 68 69 63 73 47 65 6d 73 | 0a 0a 20 20 20 20 47 65 |hicsGems|.. Ge|
|00002f10| 6e 65 72 61 6c 20 27 73 | 74 75 66 66 27 0a 20 20 |neral 's|tuff'. |
|00002f20| 20 20 66 74 70 3a 2f 2f | 77 75 61 72 63 68 69 76 | ftp://|wuarchiv|
|00002f30| 65 2e 77 75 73 74 6c 2e | 65 64 75 2f 67 72 61 70 |e.wustl.|edu/grap|
|00002f40| 68 69 63 73 2f 67 72 61 | 70 68 69 63 73 0a 0a 0a |hics/gra|phics...|
|00002f50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002f60| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002f70| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002f80| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00002f90| 2d 2d 2d 2d 2d 2d 0a 0a | 53 75 62 6a 65 63 74 3a |------..|Subject:|
|00002fa0| 20 35 29 20 48 6f 77 20 | 64 6f 20 49 20 72 6f 74 | 5) How |do I rot|
|00002fb0| 61 74 65 20 61 20 32 44 | 20 70 6f 69 6e 74 3f 0a |ate a 2D| point?.|
|00002fc0| 0a 20 20 20 20 49 6e 20 | 32 2d 44 2c 20 74 68 65 |. In |2-D, the|
|00002fd0| 20 32 78 32 20 6d 61 74 | 72 69 78 20 69 73 20 76 | 2x2 mat|rix is v|
|00002fe0| 65 72 79 20 73 69 6d 70 | 6c 65 2e 20 20 49 66 20 |ery simp|le. If |
|00002ff0| 79 6f 75 20 77 61 6e 74 | 20 74 6f 20 72 6f 74 61 |you want| to rota|
|00003000| 74 65 20 61 0a 20 20 20 | 20 63 6f 6c 75 6d 6e 20 |te a. | column |
|00003010| 76 65 63 74 6f 72 20 76 | 20 62 79 20 74 20 64 65 |vector v| by t de|
|00003020| 67 72 65 65 73 20 75 73 | 69 6e 67 20 6d 61 74 72 |grees us|ing matr|
|00003030| 69 78 20 4d 2c 20 75 73 | 65 0a 0a 20 20 20 20 20 |ix M, us|e.. |
|00003040| 20 20 20 4d 20 3d 20 7b | 7b 63 6f 73 20 74 2c 20 | M = {|{cos t, |
|00003050| 2d 73 69 6e 20 74 7d 2c | 20 7b 73 69 6e 20 74 2c |-sin t},| {sin t,|
|00003060| 20 63 6f 73 20 74 7d 7d | 20 69 6e 20 4d 2a 76 2e | cos t}}| in M*v.|
|00003070| 0a 0a 20 20 20 20 49 66 | 20 79 6f 75 20 68 61 76 |.. If| you hav|
|00003080| 65 20 61 20 72 6f 77 20 | 76 65 63 74 6f 72 2c 20 |e a row |vector, |
|00003090| 75 73 65 20 74 68 65 20 | 74 72 61 6e 73 70 6f 73 |use the |transpos|
|000030a0| 65 20 6f 66 20 4d 20 28 | 74 75 72 6e 20 72 6f 77 |e of M (|turn row|
|000030b0| 73 20 69 6e 74 6f 0a 20 | 20 20 20 63 6f 6c 75 6d |s into. | colum|
|000030c0| 6e 73 20 61 6e 64 20 76 | 69 63 65 20 76 65 72 73 |ns and v|ice vers|
|000030d0| 61 29 2e 20 20 49 66 20 | 79 6f 75 20 77 61 6e 74 |a). If |you want|
|000030e0| 20 74 6f 20 63 6f 6d 62 | 69 6e 65 20 72 6f 74 61 | to comb|ine rota|
|000030f0| 74 69 6f 6e 73 2c 20 69 | 6e 20 32 2d 44 0a 20 20 |tions, i|n 2-D. |
|00003100| 20 20 79 6f 75 20 63 61 | 6e 20 6a 75 73 74 20 61 | you ca|n just a|
|00003110| 64 64 20 74 68 65 69 72 | 20 61 6e 67 6c 65 73 2c |dd their| angles,|
|00003120| 20 62 75 74 20 69 6e 20 | 68 69 67 68 65 72 20 64 | but in |higher d|
|00003130| 69 6d 65 6e 73 69 6f 6e | 73 20 79 6f 75 20 6d 75 |imension|s you mu|
|00003140| 73 74 0a 20 20 20 20 6d | 75 6c 74 69 70 6c 79 20 |st. m|ultiply |
|00003150| 74 68 65 69 72 20 6d 61 | 74 72 69 63 65 73 2e 0a |their ma|trices..|
|00003160| 0a 0a 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |..------|--------|
|00003170| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003180| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003190| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000031a0| 2d 2d 2d 2d 2d 2d 2d 2d | 0a 0a 53 75 62 6a 65 63 |--------|..Subjec|
|000031b0| 74 3a 20 36 29 20 48 6f | 77 20 64 6f 20 49 20 72 |t: 6) Ho|w do I r|
|000031c0| 6f 74 61 74 65 20 61 20 | 33 44 20 70 6f 69 6e 74 |otate a |3D point|
|000031d0| 3f 0a 0a 20 20 20 20 41 | 73 73 75 6d 69 6e 67 20 |?.. A|ssuming |
|000031e0| 79 6f 75 20 77 61 6e 74 | 20 74 6f 20 72 6f 74 61 |you want| to rota|
|000031f0| 74 65 20 76 65 63 74 6f | 72 73 20 61 72 6f 75 6e |te vecto|rs aroun|
|00003200| 64 20 74 68 65 20 6f 72 | 69 67 69 6e 20 6f 66 20 |d the or|igin of |
|00003210| 79 6f 75 72 0a 20 20 20 | 20 63 6f 6f 72 64 69 6e |your. | coordin|
|00003220| 61 74 65 20 73 79 73 74 | 65 6d 2e 20 28 49 66 20 |ate syst|em. (If |
|00003230| 79 6f 75 20 77 61 6e 74 | 20 74 6f 20 72 6f 74 61 |you want| to rota|
|00003240| 74 65 20 61 72 6f 75 6e | 64 20 73 6f 6d 65 20 6f |te aroun|d some o|
|00003250| 74 68 65 72 20 70 6f 69 | 6e 74 2c 0a 20 20 20 20 |ther poi|nt,. |
|00003260| 73 75 62 74 72 61 63 74 | 20 69 74 73 20 63 6f 6f |subtract| its coo|
|00003270| 72 64 69 6e 61 74 65 73 | 20 66 72 6f 6d 20 74 68 |rdinates| from th|
|00003280| 65 20 70 6f 69 6e 74 20 | 79 6f 75 20 61 72 65 20 |e point |you are |
|00003290| 72 6f 74 61 74 69 6e 67 | 2c 20 64 6f 20 74 68 65 |rotating|, do the|
|000032a0| 0a 20 20 20 20 72 6f 74 | 61 74 69 6f 6e 2c 20 61 |. rot|ation, a|
|000032b0| 6e 64 20 74 68 65 6e 20 | 61 64 64 20 62 61 63 6b |nd then |add back|
|000032c0| 20 77 68 61 74 20 79 6f | 75 20 73 75 62 74 72 61 | what yo|u subtra|
|000032d0| 63 74 65 64 2e 29 20 49 | 6e 20 33 2d 44 2c 20 79 |cted.) I|n 3-D, y|
|000032e0| 6f 75 20 6e 65 65 64 0a | 20 20 20 20 6e 6f 74 20 |ou need.| not |
|000032f0| 6f 6e 6c 79 20 61 6e 20 | 61 6e 67 6c 65 2c 20 62 |only an |angle, b|
|00003300| 75 74 20 61 6c 73 6f 20 | 61 6e 20 61 78 69 73 2e |ut also |an axis.|
|00003310| 20 28 49 6e 20 68 69 67 | 68 65 72 20 64 69 6d 65 | (In hig|her dime|
|00003320| 6e 73 69 6f 6e 73 20 69 | 74 20 67 65 74 73 0a 20 |nsions i|t gets. |
|00003330| 20 20 20 6d 75 63 68 20 | 77 6f 72 73 65 2c 20 76 | much |worse, v|
|00003340| 65 72 79 20 71 75 69 63 | 6b 6c 79 2e 29 20 20 41 |ery quic|kly.) A|
|00003350| 63 74 75 61 6c 6c 79 2c | 20 79 6f 75 20 6e 65 65 |ctually,| you nee|
|00003360| 64 20 33 20 69 6e 64 65 | 70 65 6e 64 65 6e 74 0a |d 3 inde|pendent.|
|00003370| 20 20 20 20 6e 75 6d 62 | 65 72 73 2c 20 61 6e 64 | numb|ers, and|
|00003380| 20 74 68 65 73 65 20 63 | 6f 6d 65 20 69 6e 20 61 | these c|ome in a|
|00003390| 20 76 61 72 69 65 74 79 | 20 6f 66 20 66 6c 61 76 | variety| of flav|
|000033a0| 6f 72 73 2e 20 20 54 68 | 65 20 66 6c 61 76 6f 72 |ors. Th|e flavor|
|000033b0| 20 49 0a 20 20 20 20 72 | 65 63 6f 6d 6d 65 6e 64 | I. r|ecommend|
|000033c0| 20 69 73 20 75 6e 69 74 | 20 71 75 61 74 65 72 6e | is unit| quatern|
|000033d0| 69 6f 6e 73 3a 20 34 20 | 6e 75 6d 62 65 72 73 20 |ions: 4 |numbers |
|000033e0| 74 68 61 74 20 73 71 75 | 61 72 65 20 61 6e 64 20 |that squ|are and |
|000033f0| 61 64 64 20 75 70 20 74 | 6f 0a 20 20 20 20 2b 31 |add up t|o. +1|
|00003400| 2e 20 20 59 6f 75 20 63 | 61 6e 20 77 72 69 74 65 |. You c|an write|
|00003410| 20 74 68 65 73 65 20 61 | 73 20 5b 28 78 2c 79 2c | these a|s [(x,y,|
|00003420| 7a 29 2c 77 5d 2c 20 77 | 69 74 68 20 34 20 72 65 |z),w], w|ith 4 re|
|00003430| 61 6c 20 6e 75 6d 62 65 | 72 73 2c 20 6f 72 0a 20 |al numbe|rs, or. |
|00003440| 20 20 20 5b 76 2c 77 5d | 2c 20 77 69 74 68 20 76 | [v,w]|, with v|
|00003450| 2c 20 61 20 33 2d 44 20 | 76 65 63 74 6f 72 20 70 |, a 3-D |vector p|
|00003460| 6f 69 6e 74 69 6e 67 20 | 61 6c 6f 6e 67 20 74 68 |ointing |along th|
|00003470| 65 20 61 78 69 73 2e 20 | 54 68 65 20 63 6f 6e 63 |e axis. |The conc|
|00003480| 65 70 74 0a 20 20 20 20 | 6f 66 20 61 6e 20 61 78 |ept. |of an ax|
|00003490| 69 73 20 69 73 20 75 6e | 69 71 75 65 20 74 6f 20 |is is un|ique to |
|000034a0| 33 2d 44 2e 20 49 74 20 | 69 73 20 61 20 6c 69 6e |3-D. It |is a lin|
|000034b0| 65 20 74 68 72 6f 75 67 | 68 20 74 68 65 20 6f 72 |e throug|h the or|
|000034c0| 69 67 69 6e 0a 20 20 20 | 20 63 6f 6e 74 61 69 6e |igin. | contain|
|000034d0| 69 6e 67 20 61 6c 6c 20 | 74 68 65 20 70 6f 69 6e |ing all |the poin|
|000034e0| 74 73 20 77 68 69 63 68 | 20 64 6f 20 6e 6f 74 20 |ts which| do not |
|000034f0| 6d 6f 76 65 20 64 75 72 | 69 6e 67 20 74 68 65 20 |move dur|ing the |
|00003500| 72 6f 74 61 74 69 6f 6e | 2e 0a 20 20 20 20 53 6f |rotation|.. So|
|00003510| 20 77 65 20 6b 6e 6f 77 | 20 69 66 20 77 65 20 61 | we know| if we a|
|00003520| 72 65 20 74 75 72 6e 69 | 6e 67 20 66 6f 72 77 61 |re turni|ng forwa|
|00003530| 72 64 73 20 6f 72 20 62 | 61 63 6b 2c 20 77 65 20 |rds or b|ack, we |
|00003540| 75 73 65 20 61 20 76 65 | 63 74 6f 72 0a 20 20 20 |use a ve|ctor. |
|00003550| 20 70 6f 69 6e 74 69 6e | 67 20 6f 75 74 20 61 6c | pointin|g out al|
|00003560| 6f 6e 67 20 74 68 65 20 | 6c 69 6e 65 2e 20 53 75 |ong the |line. Su|
|00003570| 70 70 6f 73 65 20 79 6f | 75 20 77 61 6e 74 20 74 |ppose yo|u want t|
|00003580| 6f 20 75 73 65 20 75 6e | 69 74 20 76 65 63 74 6f |o use un|it vecto|
|00003590| 72 20 75 0a 20 20 20 20 | 61 73 20 79 6f 75 72 20 |r u. |as your |
|000035a0| 61 78 69 73 2c 20 61 6e | 64 20 72 6f 74 61 74 65 |axis, an|d rotate|
|000035b0| 20 62 79 20 32 74 20 64 | 65 67 72 65 65 73 2e 20 | by 2t d|egrees. |
|000035c0| 20 28 59 65 73 2c 20 74 | 68 61 74 27 73 20 74 77 | (Yes, t|hat's tw|
|000035d0| 69 63 65 20 74 2e 29 0a | 20 20 20 20 4d 61 6b 65 |ice t.).| Make|
|000035e0| 20 61 20 71 75 61 74 65 | 72 6e 69 6f 6e 20 5b 75 | a quate|rnion [u|
|000035f0| 20 73 69 6e 20 74 2c 20 | 63 6f 73 20 74 5d 2e 20 | sin t, |cos t]. |
|00003600| 59 6f 75 20 63 61 6e 20 | 75 73 65 20 74 68 65 20 |You can |use the |
|00003610| 71 75 61 74 65 72 6e 69 | 6f 6e 20 2d 2d 0a 20 20 |quaterni|on --. |
|00003620| 20 20 63 61 6c 6c 20 69 | 74 20 71 20 2d 2d 20 64 | call i|t q -- d|
|00003630| 69 72 65 63 74 6c 79 20 | 6f 6e 20 61 20 76 65 63 |irectly |on a vec|
|00003640| 74 6f 72 20 76 20 77 69 | 74 68 20 71 75 61 74 65 |tor v wi|th quate|
|00003650| 72 6e 69 6f 6e 0a 20 20 | 20 20 6d 75 6c 74 69 70 |rnion. | multip|
|00003660| 6c 69 63 61 74 69 6f 6e | 2c 20 71 20 76 20 71 5e |lication|, q v q^|
|00003670| 2d 31 2c 20 6f 72 20 6a | 75 73 74 20 63 6f 6e 76 |-1, or j|ust conv|
|00003680| 65 72 74 20 74 68 65 20 | 71 75 61 74 65 72 6e 69 |ert the |quaterni|
|00003690| 6f 6e 20 74 6f 20 61 20 | 33 78 33 0a 20 20 20 20 |on to a |3x3. |
|000036a0| 6d 61 74 72 69 78 20 4d | 2e 20 49 66 20 74 68 65 |matrix M|. If the|
|000036b0| 20 63 6f 6d 70 6f 6e 65 | 6e 74 73 20 6f 66 20 71 | compone|nts of q|
|000036c0| 20 61 72 65 20 7b 28 78 | 2c 79 2c 7a 29 2c 77 5d | are {(x|,y,z),w]|
|000036d0| 2c 20 74 68 65 6e 20 79 | 6f 75 20 77 61 6e 74 0a |, then y|ou want.|
|000036e0| 20 20 20 20 74 68 65 20 | 6d 61 74 72 69 78 0a 0a | the |matrix..|
|000036f0| 20 20 20 20 20 20 20 20 | 4d 20 3d 20 7b 7b 31 2d | |M = {{1-|
|00003700| 32 28 79 79 2b 7a 7a 29 | 2c 20 20 32 28 78 79 2d |2(yy+zz)|, 2(xy-|
|00003710| 77 7a 29 2c 20 20 32 28 | 78 7a 2b 77 79 29 7d 2c |wz), 2(|xz+wy)},|
|00003720| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 7b 20 |. | { |
|00003730| 20 32 28 78 79 2b 77 7a | 29 2c 31 2d 32 28 78 78 | 2(xy+wz|),1-2(xx|
|00003740| 2b 7a 7a 29 2c 20 20 32 | 28 79 7a 2d 77 78 29 7d |+zz), 2|(yz-wx)}|
|00003750| 2c 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7b |,. | {|
|00003760| 20 20 32 28 78 7a 2d 77 | 79 29 2c 20 20 32 28 79 | 2(xz-w|y), 2(y|
|00003770| 7a 2b 77 78 29 2c 31 2d | 32 28 78 78 2b 79 79 29 |z+wx),1-|2(xx+yy)|
|00003780| 7d 7d 2e 0a 0a 20 20 20 | 20 52 6f 74 61 74 69 6f |}}... | Rotatio|
|00003790| 6e 73 2c 20 74 72 61 6e | 73 6c 61 74 69 6f 6e 73 |ns, tran|slations|
|000037a0| 2c 20 61 6e 64 20 6d 75 | 63 68 20 6d 6f 72 65 20 |, and mu|ch more |
|000037b0| 61 72 65 20 65 78 70 6c | 61 69 6e 65 64 20 69 6e |are expl|ained in|
|000037c0| 20 61 6c 6c 20 62 61 73 | 69 63 0a 20 20 20 20 63 | all bas|ic. c|
|000037d0| 6f 6d 70 75 74 65 72 20 | 67 72 61 70 68 69 63 73 |omputer |graphics|
|000037e0| 20 74 65 78 74 73 2e 20 | 20 51 75 61 74 65 72 6e | texts. | Quatern|
|000037f0| 69 6f 6e 73 20 61 72 65 | 20 63 6f 76 65 72 65 64 |ions are| covered|
|00003800| 20 62 72 69 65 66 6c 79 | 20 69 6e 0a 20 20 20 20 | briefly| in. |
|00003810| 5b 46 6f 6c 65 79 5d 2c | 20 61 6e 64 20 6d 6f 72 |[Foley],| and mor|
|00003820| 65 20 65 78 74 65 6e 73 | 69 76 65 6c 79 20 69 6e |e extens|ively in|
|00003830| 20 73 65 76 65 72 61 6c | 20 47 72 61 70 68 69 63 | several| Graphic|
|00003840| 73 20 47 65 6d 73 2c 20 | 61 6e 64 20 74 68 65 0a |s Gems, |and the.|
|00003850| 20 20 20 20 53 49 47 47 | 52 41 50 48 20 38 35 20 | SIGG|RAPH 85 |
|00003860| 70 72 6f 63 65 65 64 69 | 6e 67 73 2e 0a 0a 0a 2d |proceedi|ngs....-|
|00003870| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003880| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003890| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000038a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000038b0| 2d 2d 2d 2d 2d 0a 0a 53 | 75 62 6a 65 63 74 3a 20 |-----..S|ubject: |
|000038c0| 37 29 20 48 6f 77 20 64 | 6f 20 49 20 66 69 6e 64 |7) How d|o I find|
|000038d0| 20 74 68 65 20 64 69 73 | 74 61 6e 63 65 20 66 72 | the dis|tance fr|
|000038e0| 6f 6d 20 61 20 70 6f 69 | 6e 74 20 74 6f 20 61 20 |om a poi|nt to a |
|000038f0| 6c 69 6e 65 3f 0a 0a 0a | 20 20 20 20 4c 65 74 20 |line?...| Let |
|00003900| 74 68 65 20 70 6f 69 6e | 74 20 62 65 20 43 20 28 |the poin|t be C (|
|00003910| 58 43 2c 59 43 29 20 61 | 6e 64 20 74 68 65 20 6c |XC,YC) a|nd the l|
|00003920| 69 6e 65 20 62 65 20 41 | 42 20 28 58 41 2c 59 41 |ine be A|B (XA,YA|
|00003930| 29 20 74 6f 20 28 58 42 | 2c 59 42 29 2e 0a 20 20 |) to (XB|,YB).. |
|00003940| 20 20 54 68 65 20 6c 65 | 6e 67 74 68 20 6f 66 20 | The le|ngth of |
|00003950| 74 68 65 20 6c 69 6e 65 | 20 73 65 67 6d 65 6e 74 |the line| segment|
|00003960| 20 41 42 20 69 73 20 4c | 3a 0a 0a 20 20 20 20 20 | AB is L|:.. |
|00003970| 20 20 20 4c 3d 28 28 58 | 42 2d 58 41 29 2a 2a 32 | L=((X|B-XA)**2|
|00003980| 2b 28 59 42 2d 59 41 29 | 2a 2a 32 29 2a 2a 30 2e |+(YB-YA)|**2)**0.|
|00003990| 35 0a 0a 20 20 20 20 61 | 6e 64 0a 20 20 20 20 20 |5.. a|nd. |
|000039a0| 20 20 20 20 20 20 20 28 | 59 41 2d 59 43 29 28 59 | (|YA-YC)(Y|
|000039b0| 41 2d 59 42 29 2d 28 58 | 41 2d 58 43 29 28 58 42 |A-YB)-(X|A-XC)(XB|
|000039c0| 2d 58 41 29 0a 20 20 20 | 20 20 20 20 20 72 20 3d |-XA). | r =|
|000039d0| 20 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | -------|--------|
|000039e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 0a 20 |--------|------. |
|000039f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003a00| 20 20 20 20 20 20 20 4c | 2a 2a 32 0a 0a 20 20 20 | L|**2.. |
|00003a10| 20 20 20 20 20 20 20 20 | 20 28 59 41 2d 59 43 29 | | (YA-YC)|
|00003a20| 28 58 42 2d 58 41 29 2d | 28 58 41 2d 58 43 29 28 |(XB-XA)-|(XA-XC)(|
|00003a30| 59 42 2d 59 41 29 0a 20 | 20 20 20 20 20 20 20 73 |YB-YA). | s|
|00003a40| 20 3d 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d | = -----|--------|
|00003a50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003a60| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00003a70| 20 20 20 20 20 20 20 20 | 20 4c 2a 2a 32 0a 0a 20 | | L**2.. |
|00003a80| 20 20 20 4c 65 74 20 49 | 20 62 65 20 74 68 65 20 | Let I| be the |
|00003a90| 70 6f 69 6e 74 20 6f 66 | 20 70 65 72 70 65 6e 64 |point of| perpend|
|00003aa0| 69 63 75 6c 61 72 20 70 | 72 6f 6a 65 63 74 69 6f |icular p|rojectio|
|00003ab0| 6e 20 6f 66 20 43 20 6f | 6e 74 6f 20 41 42 2c 20 |n of C o|nto AB, |
|00003ac0| 74 68 65 0a 0a 20 20 20 | 20 20 20 20 20 58 49 3d |the.. | XI=|
|00003ad0| 58 41 2b 72 28 58 42 2d | 58 41 29 0a 20 20 20 20 |XA+r(XB-|XA). |
|00003ae0| 20 20 20 20 59 49 3d 59 | 41 2b 72 28 59 42 2d 59 | YI=Y|A+r(YB-Y|
|00003af0| 41 29 0a 0a 20 20 20 20 | 44 69 73 74 61 6e 63 65 |A).. |Distance|
|00003b00| 20 66 72 6f 6d 20 41 20 | 74 6f 20 49 20 3d 20 72 | from A |to I = r|
|00003b10| 2a 4c 0a 20 20 20 20 44 | 69 73 74 61 6e 63 65 20 |*L. D|istance |
|00003b20| 66 72 6f 6d 20 43 20 74 | 6f 20 49 20 3d 20 73 2a |from C t|o I = s*|
|00003b30| 4c 0a 0a 20 20 20 20 49 | 66 20 72 3c 30 20 20 20 |L.. I|f r<0 |
|00003b40| 20 20 20 49 20 69 73 20 | 6f 6e 20 62 61 63 6b 77 | I is |on backw|
|00003b50| 61 72 64 20 65 78 74 65 | 6e 73 69 6f 6e 20 6f 66 |ard exte|nsion of|
|00003b60| 20 41 42 0a 20 20 20 20 | 49 66 20 72 3e 31 20 20 | AB. |If r>1 |
|00003b70| 20 20 20 20 49 20 69 73 | 20 6f 6e 20 61 68 65 61 | I is| on ahea|
|00003b80| 64 20 65 78 74 65 6e 73 | 69 6f 6e 20 6f 66 20 41 |d extens|ion of A|
|00003b90| 42 0a 20 20 20 20 49 66 | 20 30 3c 3d 72 3c 3d 31 |B. If| 0<=r<=1|
|00003ba0| 20 20 49 20 69 73 20 6f | 6e 20 41 42 0a 0a 20 20 | I is o|n AB.. |
|00003bb0| 20 20 49 66 20 73 3c 30 | 20 20 20 20 20 20 43 20 | If s<0| C |
|00003bc0| 69 73 20 6c 65 66 74 20 | 6f 66 20 41 42 20 28 79 |is left |of AB (y|
|00003bd0| 6f 75 20 63 61 6e 20 6a | 75 73 74 20 63 68 65 63 |ou can j|ust chec|
|00003be0| 6b 20 74 68 65 20 6e 75 | 6d 65 72 61 74 6f 72 29 |k the nu|merator)|
|00003bf0| 0a 20 20 20 20 49 66 20 | 73 3e 30 20 20 20 20 20 |. If |s>0 |
|00003c00| 20 43 20 69 73 20 72 69 | 67 68 74 20 6f 66 20 41 | C is ri|ght of A|
|00003c10| 42 0a 20 20 20 20 49 66 | 20 73 3d 30 20 20 20 20 |B. If| s=0 |
|00003c20| 20 20 43 20 69 73 20 6f | 6e 20 41 42 0a 0a 0a 2d | C is o|n AB...-|
|00003c30| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003c40| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003c50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003c60| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003c70| 2d 2d 2d 2d 2d 0a 0a 53 | 75 62 6a 65 63 74 3a 20 |-----..S|ubject: |
|00003c80| 38 29 20 48 6f 77 20 64 | 6f 20 49 20 66 69 6e 64 |8) How d|o I find|
|00003c90| 20 69 6e 74 65 72 73 65 | 63 74 69 6f 6e 73 20 6f | interse|ctions o|
|00003ca0| 66 20 32 20 32 44 20 6c | 69 6e 65 20 73 65 67 6d |f 2 2D l|ine segm|
|00003cb0| 65 6e 74 73 3f 0a 0a 20 | 20 20 20 54 68 69 73 20 |ents?.. | This |
|00003cc0| 70 72 6f 62 6c 65 6d 20 | 63 61 6e 20 62 65 20 65 |problem |can be e|
|00003cd0| 78 74 72 65 6d 65 6c 79 | 20 65 61 73 79 20 6f 72 |xtremely| easy or|
|00003ce0| 20 65 78 74 72 65 6d 65 | 6c 79 20 64 69 66 66 69 | extreme|ly diffi|
|00003cf0| 63 75 6c 74 20 64 65 70 | 65 6e 64 73 0a 20 20 20 |cult dep|ends. |
|00003d00| 20 6f 6e 20 79 6f 75 72 | 20 61 70 70 6c 69 63 61 | on your| applica|
|00003d10| 74 69 6f 6e 73 2e 20 20 | 49 66 20 61 6c 6c 20 79 |tions. |If all y|
|00003d20| 6f 75 20 77 61 6e 74 20 | 69 73 20 74 68 65 20 69 |ou want |is the i|
|00003d30| 6e 74 65 72 73 65 63 74 | 69 6f 6e 20 70 6f 69 6e |ntersect|ion poin|
|00003d40| 74 2c 0a 20 20 20 20 74 | 68 65 20 66 6f 6c 6c 6f |t,. t|he follo|
|00003d50| 77 69 6e 67 20 73 68 6f | 75 6c 64 20 77 6f 72 6b |wing sho|uld work|
|00003d60| 3a 0a 0a 20 20 20 20 4c | 65 74 20 41 2c 42 2c 43 |:.. L|et A,B,C|
|00003d70| 2c 44 20 62 65 20 32 2d | 73 70 61 63 65 20 70 6f |,D be 2-|space po|
|00003d80| 73 69 74 69 6f 6e 20 76 | 65 63 74 6f 72 73 2e 20 |sition v|ectors. |
|00003d90| 20 54 68 65 6e 20 74 68 | 65 20 64 69 72 65 63 74 | Then th|e direct|
|00003da0| 65 64 20 6c 69 6e 65 0a | 20 20 20 20 73 65 67 6d |ed line.| segm|
|00003db0| 65 6e 74 73 20 41 42 20 | 26 20 43 44 20 61 72 65 |ents AB |& CD are|
|00003dc0| 20 67 69 76 65 6e 20 62 | 79 3a 0a 0a 20 20 20 20 | given b|y:.. |
|00003dd0| 20 20 20 20 41 42 3d 41 | 2b 72 28 42 2d 41 29 2c | AB=A|+r(B-A),|
|00003de0| 20 72 20 69 6e 20 5b 30 | 2c 31 5d 0a 20 20 20 20 | r in [0|,1]. |
|00003df0| 20 20 20 20 43 44 3d 43 | 2b 73 28 44 2d 43 29 2c | CD=C|+s(D-C),|
|00003e00| 20 73 20 69 6e 20 5b 30 | 2c 31 5d 0a 0a 20 20 20 | s in [0|,1].. |
|00003e10| 20 49 66 20 41 42 20 26 | 20 43 44 20 69 6e 74 65 | If AB &| CD inte|
|00003e20| 72 73 65 63 74 2c 20 74 | 68 65 6e 0a 0a 20 20 20 |rsect, t|hen.. |
|00003e30| 20 20 20 20 20 41 2b 72 | 28 42 2d 41 29 3d 43 2b | A+r|(B-A)=C+|
|00003e40| 73 28 44 2d 43 29 2c 20 | 6f 72 0a 0a 20 20 20 20 |s(D-C), |or.. |
|00003e50| 20 20 20 20 58 41 2b 72 | 28 58 42 2d 58 41 29 3d | XA+r|(XB-XA)=|
|00003e60| 58 43 2b 73 28 58 44 2d | 58 43 29 0a 20 20 20 20 |XC+s(XD-|XC). |
|00003e70| 20 20 20 20 59 41 2b 72 | 28 59 42 2d 59 41 29 3d | YA+r|(YB-YA)=|
|00003e80| 59 43 2b 73 28 59 44 2d | 59 43 29 20 20 66 6f 72 |YC+s(YD-|YC) for|
|00003e90| 20 73 6f 6d 65 20 72 2c | 73 20 69 6e 20 5b 30 2c | some r,|s in [0,|
|00003ea0| 31 5d 0a 0a 20 20 20 20 | 53 6f 6c 76 69 6e 67 20 |1].. |Solving |
|00003eb0| 74 68 65 20 61 62 6f 76 | 65 20 66 6f 72 20 72 20 |the abov|e for r |
|00003ec0| 61 6e 64 20 73 20 79 69 | 65 6c 64 73 0a 0a 20 20 |and s yi|elds.. |
|00003ed0| 20 20 20 20 20 20 20 20 | 20 20 28 59 41 2d 59 43 | | (YA-YC|
|00003ee0| 29 28 58 44 2d 58 43 29 | 2d 28 58 41 2d 58 43 29 |)(XD-XC)|-(XA-XC)|
|00003ef0| 28 59 44 2d 59 43 29 0a | 20 20 20 20 20 20 20 20 |(YD-YC).| |
|00003f00| 72 20 3d 20 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |r = ----|--------|
|00003f10| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003f20| 2d 20 20 28 65 71 6e 20 | 31 29 0a 20 20 20 20 20 |- (eqn |1). |
|00003f30| 20 20 20 20 20 20 20 28 | 58 42 2d 58 41 29 28 59 | (|XB-XA)(Y|
|00003f40| 44 2d 59 43 29 2d 28 59 | 42 2d 59 41 29 28 58 44 |D-YC)-(Y|B-YA)(XD|
|00003f50| 2d 58 43 29 0a 0a 20 20 | 20 20 20 20 20 20 20 20 |-XC).. | |
|00003f60| 20 20 28 59 41 2d 59 43 | 29 28 58 42 2d 58 41 29 | (YA-YC|)(XB-XA)|
|00003f70| 2d 28 58 41 2d 58 43 29 | 28 59 42 2d 59 41 29 0a |-(XA-XC)|(YB-YA).|
|00003f80| 20 20 20 20 20 20 20 20 | 73 20 3d 20 2d 2d 2d 2d | |s = ----|
|00003f90| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00003fa0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 20 20 28 65 71 6e 20 |--------|- (eqn |
|00003fb0| 32 29 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |2). | (|
|00003fc0| 58 42 2d 58 41 29 28 59 | 44 2d 59 43 29 2d 28 59 |XB-XA)(Y|D-YC)-(Y|
|00003fd0| 42 2d 59 41 29 28 58 44 | 2d 58 43 29 0a 0a 20 20 |B-YA)(XD|-XC).. |
|00003fe0| 20 20 4c 65 74 20 49 20 | 62 65 20 74 68 65 20 70 | Let I |be the p|
|00003ff0| 6f 73 69 74 69 6f 6e 20 | 76 65 63 74 6f 72 20 6f |osition |vector o|
|00004000| 66 20 74 68 65 20 69 6e | 74 65 72 73 65 63 74 69 |f the in|tersecti|
|00004010| 6f 6e 20 70 6f 69 6e 74 | 2c 20 74 68 65 6e 0a 0a |on point|, then..|
|00004020| 20 20 20 20 20 20 20 20 | 49 3d 41 2b 72 28 42 2d | |I=A+r(B-|
|00004030| 41 29 20 6f 72 0a 0a 20 | 20 20 20 20 20 20 20 58 |A) or.. | X|
|00004040| 49 3d 58 41 2b 72 28 58 | 42 2d 58 41 29 0a 20 20 |I=XA+r(X|B-XA). |
|00004050| 20 20 20 20 20 20 59 49 | 3d 59 41 2b 72 28 59 42 | YI|=YA+r(YB|
|00004060| 2d 59 41 29 0a 0a 20 20 | 20 20 42 79 20 65 78 61 |-YA).. | By exa|
|00004070| 6d 69 6e 69 6e 67 20 74 | 68 65 20 76 61 6c 75 65 |mining t|he value|
|00004080| 73 20 6f 66 20 72 20 26 | 20 73 2c 20 79 6f 75 20 |s of r &| s, you |
|00004090| 63 61 6e 20 61 6c 73 6f | 20 64 65 74 65 72 6d 69 |can also| determi|
|000040a0| 6e 65 20 73 6f 6d 65 0a | 20 20 20 20 6f 74 68 65 |ne some.| othe|
|000040b0| 72 20 6c 69 6d 69 74 69 | 6e 67 20 63 6f 6e 64 69 |r limiti|ng condi|
|000040c0| 74 69 6f 6e 73 3a 0a 0a | 20 20 20 20 20 20 20 20 |tions:..| |
|000040d0| 49 66 20 30 3c 3d 72 3c | 3d 31 20 26 20 30 3c 3d |If 0<=r<|=1 & 0<=|
|000040e0| 73 3c 3d 31 2c 20 69 6e | 74 65 72 73 65 63 74 69 |s<=1, in|tersecti|
|000040f0| 6f 6e 20 65 78 69 73 74 | 73 0a 20 20 20 20 20 20 |on exist|s. |
|00004100| 20 20 20 20 20 20 72 3c | 30 20 6f 72 20 72 3e 31 | r<|0 or r>1|
|00004110| 20 6f 72 20 73 3c 30 20 | 6f 72 20 73 3e 31 20 6c | or s<0 |or s>1 l|
|00004120| 69 6e 65 20 73 65 67 6d | 65 6e 74 73 20 64 6f 20 |ine segm|ents do |
|00004130| 6e 6f 74 20 69 6e 74 65 | 72 73 65 63 74 0a 0a 20 |not inte|rsect.. |
|00004140| 20 20 20 20 20 20 20 49 | 66 20 74 68 65 20 64 65 | I|f the de|
|00004150| 6e 6f 6d 69 6e 61 74 6f | 72 20 69 6e 20 65 71 6e |nominato|r in eqn|
|00004160| 20 31 20 69 73 20 7a 65 | 72 6f 2c 20 41 42 20 26 | 1 is ze|ro, AB &|
|00004170| 20 43 44 20 61 72 65 20 | 70 61 72 61 6c 6c 65 6c | CD are |parallel|
|00004180| 0a 20 20 20 20 20 20 20 | 20 49 66 20 74 68 65 20 |. | If the |
|00004190| 6e 75 6d 65 72 61 74 6f | 72 20 69 6e 20 65 71 6e |numerato|r in eqn|
|000041a0| 20 31 20 69 73 20 61 6c | 73 6f 20 7a 65 72 6f 2c | 1 is al|so zero,|
|000041b0| 20 41 42 20 26 20 43 44 | 20 61 72 65 20 63 6f 69 | AB & CD| are coi|
|000041c0| 6e 63 69 64 65 6e 74 0a | 0a 20 20 20 20 49 66 20 |ncident.|. If |
|000041d0| 74 68 65 20 69 6e 74 65 | 72 73 65 63 74 69 6f 6e |the inte|rsection|
|000041e0| 20 70 6f 69 6e 74 20 6f | 66 20 74 68 65 20 32 20 | point o|f the 2 |
|000041f0| 6c 69 6e 65 73 20 61 72 | 65 20 6e 65 65 64 65 64 |lines ar|e needed|
|00004200| 20 28 6c 69 6e 65 73 20 | 69 6e 20 74 68 69 73 0a | (lines |in this.|
|00004210| 20 20 20 20 63 6f 6e 74 | 65 78 74 20 6d 65 61 6e | cont|ext mean|
|00004220| 20 69 6e 66 69 6e 69 74 | 65 20 6c 69 6e 65 73 29 | infinit|e lines)|
|00004230| 20 72 65 67 61 72 64 6c | 65 73 73 20 77 68 65 74 | regardl|ess whet|
|00004240| 68 65 72 20 74 68 65 20 | 74 77 6f 20 6c 69 6e 65 |her the |two line|
|00004250| 0a 20 20 20 20 73 65 67 | 6d 65 6e 74 73 20 69 6e |. seg|ments in|
|00004260| 74 65 72 73 65 63 74 2c | 20 74 68 65 6e 0a 0a 20 |tersect,| then.. |
|00004270| 20 20 20 20 20 20 20 49 | 66 20 72 3e 31 2c 20 49 | I|f r>1, I|
|00004280| 20 69 73 20 6c 6f 63 61 | 74 65 64 20 6f 6e 20 65 | is loca|ted on e|
|00004290| 78 74 65 6e 73 69 6f 6e | 20 6f 66 20 41 42 0a 20 |xtension| of AB. |
|000042a0| 20 20 20 20 20 20 20 49 | 66 20 72 3c 30 2c 20 49 | I|f r<0, I|
|000042b0| 20 69 73 20 6c 6f 63 61 | 74 65 64 20 6f 6e 20 65 | is loca|ted on e|
|000042c0| 78 74 65 6e 73 69 6f 6e | 20 6f 66 20 42 41 0a 20 |xtension| of BA. |
|000042d0| 20 20 20 20 20 20 20 49 | 66 20 73 3e 31 2c 20 49 | I|f s>1, I|
|000042e0| 20 69 73 20 6c 6f 63 61 | 74 65 64 20 6f 6e 20 65 | is loca|ted on e|
|000042f0| 78 74 65 6e 73 69 6f 6e | 20 6f 66 20 43 44 0a 20 |xtension| of CD. |
|00004300| 20 20 20 20 20 20 20 49 | 66 20 73 3c 30 2c 20 49 | I|f s<0, I|
|00004310| 20 69 73 20 6c 6f 63 61 | 74 65 64 20 6f 6e 20 65 | is loca|ted on e|
|00004320| 78 74 65 6e 73 69 6f 6e | 20 6f 66 20 44 43 0a 0a |xtension| of DC..|
|00004330| 20 20 20 20 41 6c 73 6f | 20 6e 6f 74 65 20 74 68 | Also| note th|
|00004340| 61 74 20 74 68 65 20 64 | 65 6e 6f 6d 69 6e 61 74 |at the d|enominat|
|00004350| 6f 72 73 20 6f 66 20 65 | 71 6e 20 31 20 26 20 32 |ors of e|qn 1 & 2|
|00004360| 20 61 72 65 20 69 64 65 | 6e 74 69 63 61 6c 2e 0a | are ide|ntical..|
|00004370| 0a 20 20 20 20 52 65 66 | 65 72 65 6e 63 65 73 3a |. Ref|erences:|
|00004380| 0a 0a 20 20 20 20 5b 4f | 27 52 6f 75 72 6b 65 5d |.. [O|'Rourke]|
|00004390| 20 70 70 2e 20 32 34 39 | 2d 35 31 0a 20 20 20 20 | pp. 249|-51. |
|000043a0| 5b 47 65 6d 73 20 49 49 | 49 5d 20 70 70 2e 20 31 |[Gems II|I] pp. 1|
|000043b0| 39 39 2d 32 30 32 20 22 | 46 61 73 74 65 72 20 4c |99-202 "|Faster L|
|000043c0| 69 6e 65 20 53 65 67 6d | 65 6e 74 20 49 6e 74 65 |ine Segm|ent Inte|
|000043d0| 72 73 65 63 74 69 6f 6e | 2c 22 0a 0a 0a 2d 2d 2d |rsection|,"...---|
|000043e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000043f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004400| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004410| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004420| 2d 2d 2d 0a 0a 53 75 62 | 6a 65 63 74 3a 20 39 29 |---..Sub|ject: 9)|
|00004430| 20 48 6f 77 20 64 6f 20 | 49 20 66 69 6e 64 20 74 | How do |I find t|
|00004440| 68 65 20 69 6e 74 65 72 | 73 65 63 74 69 6f 6e 20 |he inter|section |
|00004450| 6f 66 20 61 20 6c 69 6e | 65 20 61 6e 64 20 61 20 |of a lin|e and a |
|00004460| 70 6c 61 6e 65 3f 0a 0a | 20 20 20 20 49 66 20 74 |plane?..| If t|
|00004470| 68 65 20 70 6c 61 6e 65 | 20 69 73 20 64 65 66 69 |he plane| is defi|
|00004480| 6e 65 64 20 61 73 3a 0a | 0a 20 20 20 20 20 20 20 |ned as:.|. |
|00004490| 20 61 2a 78 20 2b 20 62 | 2a 79 20 2b 20 63 2a 7a | a*x + b|*y + c*z|
|000044a0| 20 2b 20 64 20 3d 20 30 | 0a 0a 20 20 20 20 61 6e | + d = 0|.. an|
|000044b0| 64 20 74 68 65 20 6c 69 | 6e 65 20 69 73 20 64 65 |d the li|ne is de|
|000044c0| 66 69 6e 65 64 20 61 73 | 3a 0a 0a 20 20 20 20 20 |fined as|:.. |
|000044d0| 20 20 20 78 20 3d 20 78 | 31 20 2b 20 28 78 32 20 | x = x|1 + (x2 |
|000044e0| 2d 20 78 31 29 2a 74 20 | 3d 20 78 31 20 2b 20 69 |- x1)*t |= x1 + i|
|000044f0| 2a 74 0a 20 20 20 20 20 | 20 20 20 79 20 3d 20 79 |*t. | y = y|
|00004500| 31 20 2b 20 28 79 32 20 | 2d 20 79 31 29 2a 74 20 |1 + (y2 |- y1)*t |
|00004510| 3d 20 79 31 20 2b 20 6a | 2a 74 0a 20 20 20 20 20 |= y1 + j|*t. |
|00004520| 20 20 20 7a 20 3d 20 7a | 31 20 2b 20 28 7a 32 20 | z = z|1 + (z2 |
|00004530| 2d 20 7a 31 29 2a 74 20 | 3d 20 7a 31 20 2b 20 6b |- z1)*t |= z1 + k|
|00004540| 2a 74 0a 0a 20 20 20 20 | 54 68 65 6e 20 6a 75 73 |*t.. |Then jus|
|00004550| 74 20 73 75 62 73 74 69 | 74 75 74 65 20 74 68 65 |t substi|tute the|
|00004560| 73 65 20 69 6e 74 6f 20 | 74 68 65 20 70 6c 61 6e |se into |the plan|
|00004570| 65 20 65 71 75 61 74 69 | 6f 6e 2e 20 59 6f 75 20 |e equati|on. You |
|00004580| 65 6e 64 20 75 70 0a 20 | 20 20 20 77 69 74 68 3a |end up. | with:|
|00004590| 0a 0a 20 20 20 20 20 20 | 20 20 74 20 3d 20 2d 20 |.. | t = - |
|000045a0| 28 61 2a 78 31 20 2b 20 | 62 2a 79 31 20 2b 20 63 |(a*x1 + |b*y1 + c|
|000045b0| 2a 7a 31 20 2b 20 64 29 | 2f 28 61 2a 69 20 2b 20 |*z1 + d)|/(a*i + |
|000045c0| 62 2a 6a 20 2b 20 63 2a | 6b 29 0a 0a 20 20 20 20 |b*j + c*|k).. |
|000045d0| 49 66 20 74 68 65 20 64 | 65 6e 6f 6d 69 6e 61 74 |If the d|enominat|
|000045e0| 6f 72 20 69 73 20 7a 65 | 72 6f 2c 20 74 68 65 6e |or is ze|ro, then|
|000045f0| 20 74 68 65 20 76 65 63 | 74 6f 72 20 28 61 2c 62 | the vec|tor (a,b|
|00004600| 2c 63 29 20 61 6e 64 20 | 74 68 65 20 76 65 63 74 |,c) and |the vect|
|00004610| 6f 72 0a 20 20 20 20 28 | 69 2c 6a 2c 6b 29 20 61 |or. (|i,j,k) a|
|00004620| 72 65 20 70 65 72 70 65 | 6e 64 69 63 75 6c 61 72 |re perpe|ndicular|
|00004630| 2e 20 20 4e 6f 74 65 20 | 74 68 61 74 20 28 61 2c |. Note |that (a,|
|00004640| 62 2c 63 29 20 69 73 20 | 74 68 65 20 6e 6f 72 6d |b,c) is |the norm|
|00004650| 61 6c 20 74 6f 20 74 68 | 65 0a 20 20 20 20 70 6c |al to th|e. pl|
|00004660| 61 6e 65 20 61 6e 64 20 | 28 69 2c 6a 2c 6b 29 20 |ane and |(i,j,k) |
|00004670| 69 73 20 74 68 65 20 64 | 69 72 65 63 74 69 6f 6e |is the d|irection|
|00004680| 20 6f 66 20 74 68 65 20 | 6c 69 6e 65 2e 20 20 49 | of the |line. I|
|00004690| 74 20 66 6f 6c 6c 6f 77 | 73 20 74 68 61 74 0a 20 |t follow|s that. |
|000046a0| 20 20 20 74 68 65 20 6c | 69 6e 65 20 69 73 20 65 | the l|ine is e|
|000046b0| 69 74 68 65 72 20 70 61 | 72 61 6c 6c 65 6c 20 74 |ither pa|rallel t|
|000046c0| 6f 20 74 68 65 20 70 6c | 61 6e 65 20 6f 72 20 63 |o the pl|ane or c|
|000046d0| 6f 6e 74 61 69 6e 65 64 | 20 69 6e 20 74 68 65 0a |ontained| in the.|
|000046e0| 20 20 20 20 70 6c 61 6e | 65 2e 20 49 6e 20 65 69 | plan|e. In ei|
|000046f0| 74 68 65 72 20 63 61 73 | 65 20 74 68 65 72 65 20 |ther cas|e there |
|00004700| 69 73 20 6e 6f 20 75 6e | 69 71 75 65 20 69 6e 74 |is no un|ique int|
|00004710| 65 72 73 65 63 74 69 6f | 6e 20 70 6f 69 6e 74 2e |ersectio|n point.|
|00004720| 0a 0a 0a 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |...-----|--------|
|00004730| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004740| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004750| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004760| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 0a 0a 53 75 62 6a 65 |--------|-..Subje|
|00004770| 63 74 3a 20 31 30 29 20 | 48 6f 77 20 64 6f 20 49 |ct: 10) |How do I|
|00004780| 20 72 6f 74 61 74 65 20 | 61 20 62 69 74 6d 61 70 | rotate |a bitmap|
|00004790| 3f 0a 0a 20 20 20 20 54 | 68 65 20 65 61 73 69 65 |?.. T|he easie|
|000047a0| 73 74 20 77 61 79 2c 20 | 61 63 63 6f 72 64 69 6e |st way, |accordin|
|000047b0| 67 20 74 6f 20 74 68 65 | 20 63 6f 6d 70 2e 67 72 |g to the| comp.gr|
|000047c0| 61 70 68 69 63 73 20 66 | 61 71 2c 20 69 73 20 74 |aphics f|aq, is t|
|000047d0| 6f 20 74 61 6b 65 0a 20 | 20 20 20 74 68 65 20 72 |o take. | the r|
|000047e0| 6f 74 61 74 69 6f 6e 20 | 74 72 61 6e 73 66 6f 72 |otation |transfor|
|000047f0| 6d 61 74 69 6f 6e 20 61 | 6e 64 20 69 6e 76 65 72 |mation a|nd inver|
|00004800| 74 20 69 74 2e 20 54 68 | 65 6e 20 79 6f 75 20 6a |t it. Th|en you j|
|00004810| 75 73 74 20 69 74 65 72 | 61 74 65 0a 20 20 20 20 |ust iter|ate. |
|00004820| 6f 76 65 72 20 74 68 65 | 20 64 65 73 74 69 6e 61 |over the| destina|
|00004830| 74 69 6f 6e 20 69 6d 61 | 67 65 2c 20 61 70 70 6c |tion ima|ge, appl|
|00004840| 79 20 74 68 69 73 20 69 | 6e 76 65 72 73 65 20 74 |y this i|nverse t|
|00004850| 72 61 6e 73 66 6f 72 6d | 61 74 69 6f 6e 20 61 6e |ransform|ation an|
|00004860| 64 0a 20 20 20 20 66 69 | 6e 64 20 77 68 69 63 68 |d. fi|nd which|
|00004870| 20 73 6f 75 72 63 65 20 | 70 69 78 65 6c 20 74 6f | source |pixel to|
|00004880| 20 63 6f 70 79 20 74 68 | 65 72 65 2e 0a 0a 20 20 | copy th|ere... |
|00004890| 20 20 41 20 6d 75 63 68 | 20 6e 69 63 65 72 20 77 | A much| nicer w|
|000048a0| 61 79 20 63 6f 6d 65 73 | 20 66 72 6f 6d 20 74 68 |ay comes| from th|
|000048b0| 65 20 6f 62 73 65 72 76 | 61 74 69 6f 6e 20 74 68 |e observ|ation th|
|000048c0| 61 74 20 74 68 65 20 72 | 6f 74 61 74 69 6f 6e 0a |at the r|otation.|
|000048d0| 20 20 20 20 6d 61 74 72 | 69 78 3a 0a 0a 20 20 20 | matr|ix:.. |
|000048e0| 20 20 20 20 20 52 28 54 | 29 20 3d 20 7b 20 7b 20 | R(T|) = { { |
|000048f0| 63 6f 73 28 54 29 2c 20 | 2d 73 69 6e 28 54 29 20 |cos(T), |-sin(T) |
|00004900| 7d 2c 20 7b 20 73 69 6e | 28 54 29 2c 20 63 6f 73 |}, { sin|(T), cos|
|00004910| 28 54 29 20 7d 20 7d 0a | 0a 20 20 20 20 69 73 20 |(T) } }.|. is |
|00004920| 66 6f 72 6d 65 64 20 6d | 79 20 6d 75 6c 74 69 70 |formed m|y multip|
|00004930| 6c 79 69 6e 67 20 74 68 | 72 65 65 20 6d 61 74 72 |lying th|ree matr|
|00004940| 69 63 65 73 2c 20 6e 61 | 6d 65 6c 79 3a 0a 0a 20 |ices, na|mely:.. |
|00004950| 20 20 20 20 20 20 20 52 | 28 54 29 20 3d 20 4d 31 | R|(T) = M1|
|00004960| 28 54 29 20 2a 20 4d 32 | 28 54 29 20 2a 20 4d 33 |(T) * M2|(T) * M3|
|00004970| 28 54 29 0a 0a 20 20 20 | 20 77 68 65 72 65 0a 0a |(T).. | where..|
|00004980| 20 20 20 20 20 20 20 20 | 4d 31 28 54 29 20 3d 20 | |M1(T) = |
|00004990| 7b 20 7b 20 31 2c 20 2d | 74 61 6e 28 54 2f 32 29 |{ { 1, -|tan(T/2)|
|000049a0| 20 7d 2c 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | },. | |
|000049b0| 20 20 20 20 20 20 7b 20 | 30 2c 20 31 20 20 20 20 | { |0, 1 |
|000049c0| 20 20 20 20 20 7d 20 7d | 0a 20 20 20 20 20 20 20 | } }|. |
|000049d0| 20 4d 32 28 54 29 20 3d | 20 7b 20 7b 20 31 2c 20 | M2(T) =| { { 1, |
|000049e0| 20 20 20 20 20 30 20 20 | 20 20 7d 2c 0a 20 20 20 | 0 | },. |
|000049f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7b | | {|
|00004a00| 20 73 69 6e 28 54 29 2c | 20 31 20 20 20 20 7d 20 | sin(T),| 1 } |
|00004a10| 7d 0a 20 20 20 20 20 20 | 20 20 4d 33 28 54 29 20 |}. | M3(T) |
|00004a20| 3d 20 7b 20 7b 20 31 2c | 20 2d 74 61 6e 28 54 2f |= { { 1,| -tan(T/|
|00004a30| 32 29 20 7d 2c 0a 20 20 | 20 20 20 20 20 20 20 20 |2) },. | |
|00004a40| 20 20 20 20 20 20 20 20 | 7b 20 30 2c 20 20 20 20 | |{ 0, |
|00004a50| 20 20 20 20 20 31 20 7d | 20 7d 0a 0a 20 20 20 20 | 1 }| }.. |
|00004a60| 45 61 63 68 20 74 72 61 | 6e 73 66 6f 72 6d 61 74 |Each tra|nsformat|
|00004a70| 69 6f 6e 20 63 61 6e 20 | 62 65 20 70 65 72 66 6f |ion can |be perfo|
|00004a80| 72 6d 65 64 20 69 6e 20 | 61 20 73 65 70 61 72 61 |rmed in |a separa|
|00004a90| 74 65 20 70 61 73 73 2c | 20 61 6e 64 0a 20 20 20 |te pass,| and. |
|00004aa0| 20 62 65 63 61 75 73 65 | 20 74 68 65 73 65 20 74 | because| these t|
|00004ab0| 72 61 6e 73 66 6f 72 6d | 61 74 69 6f 6e 73 20 61 |ransform|ations a|
|00004ac0| 72 65 20 65 69 74 68 65 | 72 20 72 6f 77 2d 70 72 |re eithe|r row-pr|
|00004ad0| 65 73 65 72 76 69 6e 67 | 20 6f 72 0a 20 20 20 20 |eserving| or. |
|00004ae0| 63 6f 6c 75 6d 6e 2d 70 | 72 65 73 65 72 76 69 6e |column-p|reservin|
|00004af0| 67 2c 20 61 6e 74 69 2d | 61 6c 69 61 73 69 6e 67 |g, anti-|aliasing|
|00004b00| 20 69 73 20 71 75 69 74 | 65 20 65 61 73 79 2e 0a | is quit|e easy..|
|00004b10| 0a 20 20 20 20 52 65 66 | 65 72 65 6e 63 65 3a 0a |. Ref|erence:.|
|00004b20| 0a 20 20 20 20 50 61 65 | 74 68 2c 20 41 2e 20 57 |. Pae|th, A. W|
|00004b30| 2e 2c 20 22 41 20 46 61 | 73 74 20 41 6c 67 6f 72 |., "A Fa|st Algor|
|00004b40| 69 74 68 6d 20 66 6f 72 | 20 47 65 6e 65 72 61 6c |ithm for| General|
|00004b50| 20 52 61 73 74 65 72 20 | 52 6f 74 61 74 69 6f 6e | Raster |Rotation|
|00004b60| 22 2c 0a 20 20 20 20 50 | 72 6f 63 65 65 64 69 6e |",. P|roceedin|
|00004b70| 67 73 20 47 72 61 70 68 | 69 63 73 20 49 6e 74 65 |gs Graph|ics Inte|
|00004b80| 72 66 61 63 65 20 27 38 | 39 2c 20 43 61 6e 61 64 |rface '8|9, Canad|
|00004b90| 69 61 6e 20 49 6e 66 6f | 72 6d 61 74 69 6f 6e 0a |ian Info|rmation.|
|00004ba0| 20 20 20 20 50 72 6f 63 | 65 73 73 69 6e 67 20 53 | Proc|essing S|
|00004bb0| 6f 63 69 65 74 79 2c 20 | 31 39 38 36 2c 20 37 37 |ociety, |1986, 77|
|00004bc0| 2d 38 31 0a 20 20 20 20 | 5b 4e 6f 74 65 20 2d 20 |-81. |[Note - |
|00004bd0| 65 2d 6d 61 69 6c 20 63 | 6f 70 69 65 73 20 6f 66 |e-mail c|opies of|
|00004be0| 20 74 68 69 73 20 70 61 | 70 65 72 20 61 72 65 20 | this pa|per are |
|00004bf0| 6e 6f 20 6c 6f 6e 67 65 | 72 20 61 76 61 69 6c 61 |no longe|r availa|
|00004c00| 62 6c 65 5d 0a 0a 20 20 | 20 20 5b 47 65 6d 73 20 |ble].. | [Gems |
|00004c10| 49 5d 0a 0a 0a 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |I]...---|--------|
|00004c20| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004c30| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004c40| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004c50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 0a 0a 53 75 62 |--------|---..Sub|
|00004c60| 6a 65 63 74 3a 20 31 31 | 29 20 48 6f 77 20 64 6f |ject: 11|) How do|
|00004c70| 20 49 20 64 69 73 70 6c | 61 79 20 61 20 32 34 20 | I displ|ay a 24 |
|00004c80| 62 69 74 20 69 6d 61 67 | 65 20 69 6e 20 38 20 62 |bit imag|e in 8 b|
|00004c90| 69 74 73 3f 0a 0a 20 20 | 20 20 5b 47 65 6d 73 20 |its?.. | [Gems |
|00004ca0| 49 5d 20 70 70 2e 20 32 | 38 37 2d 32 39 33 2c 20 |I] pp. 2|87-293, |
|00004cb0| 22 41 20 53 69 6d 70 6c | 65 20 4d 65 74 68 6f 64 |"A Simpl|e Method|
|00004cc0| 20 66 6f 72 20 43 6f 6c | 6f 72 20 51 75 61 6e 74 | for Col|or Quant|
|00004cd0| 69 7a 61 74 69 6f 6e 3a | 0a 20 20 20 20 4f 63 74 |ization:|. Oct|
|00004ce0| 72 65 65 20 51 75 61 6e | 74 69 7a 61 74 69 6f 6e |ree Quan|tization|
|00004cf0| 22 0a 0a 20 20 20 20 42 | 2e 20 4b 75 72 7a 2e 20 |".. B|. Kurz. |
|00004d00| 20 4f 70 74 69 6d 61 6c | 20 43 6f 6c 6f 72 20 51 | Optimal| Color Q|
|00004d10| 75 61 6e 74 69 7a 61 74 | 69 6f 6e 20 66 6f 72 20 |uantizat|ion for |
|00004d20| 43 6f 6c 6f 72 20 44 69 | 73 70 6c 61 79 73 2e 0a |Color Di|splays..|
|00004d30| 20 20 20 20 50 72 6f 63 | 65 65 64 69 6e 67 73 20 | Proc|eedings |
|00004d40| 6f 66 20 74 68 65 20 49 | 45 45 45 20 43 6f 6e 66 |of the I|EEE Conf|
|00004d50| 65 72 65 6e 63 65 20 6f | 6e 20 43 6f 6d 70 75 74 |erence o|n Comput|
|00004d60| 65 72 20 56 69 73 69 6f | 6e 20 61 6e 64 20 50 61 |er Visio|n and Pa|
|00004d70| 74 74 65 72 6e 0a 20 20 | 20 20 52 65 63 6f 67 6e |ttern. | Recogn|
|00004d80| 69 74 69 6f 6e 2c 20 31 | 39 38 33 2c 20 70 70 2e |ition, 1|983, pp.|
|00004d90| 20 32 31 37 2d 32 32 34 | 2e 0a 0a 20 20 20 20 5b | 217-224|... [|
|00004da0| 47 65 6d 73 20 49 49 5d | 20 70 70 2e 20 31 31 36 |Gems II]| pp. 116|
|00004db0| 2d 31 32 35 2c 20 22 45 | 66 66 69 63 69 65 6e 74 |-125, "E|fficient|
|00004dc0| 20 49 6e 76 65 72 73 65 | 20 43 6f 6c 6f 72 20 4d | Inverse| Color M|
|00004dd0| 61 70 20 43 6f 6d 70 75 | 74 61 74 69 6f 6e 22 0a |ap Compu|tation".|
|00004de0| 0a 20 20 20 20 20 20 20 | 20 54 68 69 73 20 64 65 |. | This de|
|00004df0| 73 63 72 69 62 65 73 20 | 61 6e 20 65 66 66 69 63 |scribes |an effic|
|00004e00| 69 65 6e 74 20 74 65 63 | 68 6e 69 71 75 65 20 74 |ient tec|hnique t|
|00004e10| 6f 0a 20 20 20 20 20 20 | 20 20 6d 61 70 20 61 63 |o. | map ac|
|00004e20| 74 75 61 6c 20 63 6f 6c | 6f 72 73 20 74 6f 20 61 |tual col|ors to a|
|00004e30| 20 72 65 64 75 63 65 64 | 20 63 6f 6c 6f 72 20 6d | reduced| color m|
|00004e40| 61 70 2c 0a 20 20 20 20 | 20 20 20 20 73 65 6c 65 |ap,. | sele|
|00004e50| 63 74 65 64 20 62 79 20 | 73 6f 6d 65 20 6f 74 68 |cted by |some oth|
|00004e60| 65 72 20 74 65 63 68 6e | 69 71 75 65 20 64 65 73 |er techn|ique des|
|00004e70| 63 72 69 62 65 64 0a 20 | 20 20 20 20 20 20 20 69 |cribed. | i|
|00004e80| 6e 20 74 68 65 20 6f 74 | 68 65 72 20 70 61 70 65 |n the ot|her pape|
|00004e90| 72 73 2e 0a 0a 20 20 20 | 20 5b 47 65 6d 73 20 49 |rs... | [Gems I|
|00004ea0| 49 5d 20 70 70 2e 20 31 | 32 36 2d 31 33 33 2c 20 |I] pp. 1|26-133, |
|00004eb0| 22 45 66 66 69 63 69 65 | 6e 74 20 53 74 61 74 69 |"Efficie|nt Stati|
|00004ec0| 73 74 69 63 61 6c 20 43 | 6f 6d 70 75 74 61 74 69 |stical C|omputati|
|00004ed0| 6f 6e 73 20 66 6f 72 0a | 20 20 20 20 4f 70 74 69 |ons for.| Opti|
|00004ee0| 6d 61 6c 20 43 6f 6c 6f | 72 20 51 75 61 6e 74 69 |mal Colo|r Quanti|
|00004ef0| 7a 61 74 69 6f 6e 22 0a | 0a 20 20 20 20 58 69 61 |zation".|. Xia|
|00004f00| 6f 6c 69 6e 20 57 75 2e | 20 20 43 6f 6c 6f 72 20 |olin Wu.| Color |
|00004f10| 51 75 61 6e 74 69 7a 61 | 74 69 6f 6e 20 62 79 20 |Quantiza|tion by |
|00004f20| 44 79 6e 61 6d 69 63 20 | 50 72 6f 67 72 61 6d 6d |Dynamic |Programm|
|00004f30| 69 6e 67 20 61 6e 64 0a | 20 20 20 20 50 72 69 6e |ing and.| Prin|
|00004f40| 63 69 70 61 6c 20 41 6e | 61 6c 79 73 69 73 2e 20 |cipal An|alysis. |
|00004f50| 20 41 43 4d 20 54 72 61 | 6e 73 61 63 74 69 6f 6e | ACM Tra|nsaction|
|00004f60| 73 20 6f 6e 20 47 72 61 | 70 68 69 63 73 2c 20 56 |s on Gra|phics, V|
|00004f70| 6f 6c 2e 20 31 31 2c 20 | 4e 6f 2e 20 34 2c 0a 20 |ol. 11, |No. 4,. |
|00004f80| 20 20 20 4f 63 74 6f 62 | 65 72 20 31 39 39 32 2c | Octob|er 1992,|
|00004f90| 20 70 70 20 33 34 38 2d | 33 37 32 2e 0a 0a 0a 2d | pp 348-|372....-|
|00004fa0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004fb0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004fc0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004fd0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00004fe0| 2d 2d 2d 2d 2d 0a 0a 53 | 75 62 6a 65 63 74 3a 20 |-----..S|ubject: |
|00004ff0| 31 32 29 20 48 6f 77 20 | 64 6f 20 49 20 66 69 6c |12) How |do I fil|
|00005000| 6c 20 74 68 65 20 61 72 | 65 61 20 6f 66 20 61 6e |l the ar|ea of an|
|00005010| 20 61 72 62 69 74 72 61 | 72 79 20 73 68 61 70 65 | arbitra|ry shape|
|00005020| 3f 0a 0a 0a 20 20 20 20 | 22 41 20 46 61 73 74 20 |?... |"A Fast |
|00005030| 41 6c 67 6f 72 69 74 68 | 6d 20 66 6f 72 20 74 68 |Algorith|m for th|
|00005040| 65 20 52 65 73 74 6f 72 | 61 74 69 6f 6e 20 6f 66 |e Restor|ation of|
|00005050| 20 49 6d 61 67 65 73 20 | 42 61 73 65 64 20 6f 6e | Images |Based on|
|00005060| 20 43 68 61 69 6e 0a 20 | 20 20 20 20 20 20 20 43 | Chain. | C|
|00005070| 6f 64 65 73 20 44 65 73 | 63 72 69 70 74 69 6f 6e |odes Des|cription|
|00005080| 20 61 6e 64 20 49 74 73 | 20 41 70 70 6c 69 63 61 | and Its| Applica|
|00005090| 74 69 6f 6e 73 22 2c 20 | 4c 2e 57 2e 20 43 68 61 |tions", |L.W. Cha|
|000050a0| 6e 67 20 26 20 4b 2e 4c | 2e 20 4c 65 75 2c 0a 20 |ng & K.L|. Leu,. |
|000050b0| 20 20 20 20 20 20 20 43 | 6f 6d 70 75 74 65 72 20 | C|omputer |
|000050c0| 56 69 73 69 6f 6e 2c 20 | 47 72 61 70 68 69 63 73 |Vision, |Graphics|
|000050d0| 2c 20 61 6e 64 20 49 6d | 61 67 65 20 50 72 6f 63 |, and Im|age Proc|
|000050e0| 65 73 73 69 6e 67 2c 20 | 76 6f 6c 2e 35 30 2c 0a |essing, |vol.50,.|
|000050f0| 20 20 20 20 20 20 20 20 | 70 70 32 39 36 2d 33 30 | |pp296-30|
|00005100| 37 20 28 31 39 39 30 29 | 0a 0a 20 20 20 20 22 41 |7 (1990)|.. "A|
|00005110| 6e 20 49 6e 74 72 6f 64 | 75 63 74 6f 72 79 20 43 |n Introd|uctory C|
|00005120| 6f 75 72 73 65 20 69 6e | 20 43 6f 6d 70 75 74 65 |ourse in| Compute|
|00005130| 72 20 47 72 61 70 68 69 | 63 73 22 20 62 79 20 52 |r Graphi|cs" by R|
|00005140| 69 63 68 61 72 64 20 4b | 69 6e 67 73 6c 61 6b 65 |ichard K|ingslake|
|00005150| 2c 0a 20 20 20 20 20 20 | 20 20 28 32 6e 64 20 65 |,. | (2nd e|
|00005160| 64 69 74 69 6f 6e 29 20 | 70 75 62 6c 69 73 68 65 |dition) |publishe|
|00005170| 64 20 62 79 20 43 68 61 | 72 74 77 65 6c 6c 2d 42 |d by Cha|rtwell-B|
|00005180| 72 61 74 74 20 49 53 42 | 4e 20 30 2d 38 36 32 33 |ratt ISB|N 0-8623|
|00005190| 38 2d 32 38 34 2d 58 0a | 0a 20 20 20 20 5b 47 65 |8-284-X.|. [Ge|
|000051a0| 6d 73 20 49 5d 0a 20 20 | 20 20 5b 46 6f 6c 65 79 |ms I]. | [Foley|
|000051b0| 5d 0a 20 20 20 20 5b 48 | 65 61 72 6e 5d 0a 0a 0a |]. [H|earn]...|
|000051c0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000051d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000051e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000051f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005200| 2d 2d 2d 2d 2d 2d 0a 0a | 53 75 62 6a 65 63 74 3a |------..|Subject:|
|00005210| 20 31 33 29 20 48 6f 77 | 20 64 6f 20 49 20 66 69 | 13) How| do I fi|
|00005220| 6e 64 20 74 68 65 20 27 | 65 64 67 65 73 27 20 69 |nd the '|edges' i|
|00005230| 6e 20 61 20 62 69 74 6d | 61 70 3f 0a 0a 20 20 20 |n a bitm|ap?.. |
|00005240| 20 41 20 73 69 6d 70 6c | 65 20 6d 65 74 68 6f 64 | A simpl|e method|
|00005250| 20 69 73 20 74 6f 20 70 | 75 74 20 74 68 65 20 62 | is to p|ut the b|
|00005260| 69 74 6d 61 70 20 74 68 | 72 6f 75 67 68 20 74 68 |itmap th|rough th|
|00005270| 65 20 66 69 6c 74 65 72 | 3a 0a 0a 20 20 20 20 20 |e filter|:.. |
|00005280| 20 20 20 2d 31 20 20 20 | 20 2d 31 20 20 20 20 2d | -1 | -1 -|
|00005290| 31 0a 20 20 20 20 20 20 | 20 20 2d 31 20 20 20 20 |1. | -1 |
|000052a0| 20 38 20 20 20 20 2d 31 | 0a 20 20 20 20 20 20 20 | 8 -1|. |
|000052b0| 20 2d 31 20 20 20 20 2d | 31 20 20 20 20 2d 31 0a | -1 -|1 -1.|
|000052c0| 0a 20 20 20 20 54 68 69 | 73 20 77 69 6c 6c 20 68 |. Thi|s will h|
|000052d0| 69 67 68 6c 69 67 68 74 | 20 63 68 61 6e 67 65 73 |ighlight| changes|
|000052e0| 20 69 6e 20 63 6f 6e 74 | 72 61 73 74 2e 20 20 54 | in cont|rast. T|
|000052f0| 68 65 6e 20 61 6e 79 20 | 70 61 72 74 20 6f 66 20 |hen any |part of |
|00005300| 74 68 65 0a 20 20 20 20 | 70 69 63 74 75 72 65 20 |the. |picture |
|00005310| 77 68 65 72 65 20 74 68 | 65 20 61 62 73 6f 6c 75 |where th|e absolu|
|00005320| 74 65 20 66 69 6c 74 65 | 72 65 64 20 76 61 6c 75 |te filte|red valu|
|00005330| 65 20 69 73 20 68 69 67 | 68 65 72 20 74 68 61 6e |e is hig|her than|
|00005340| 20 73 6f 6d 65 0a 20 20 | 20 20 74 68 72 65 73 68 | some. | thresh|
|00005350| 6f 6c 64 20 69 73 20 61 | 6e 20 22 65 64 67 65 22 |old is a|n "edge"|
|00005360| 2e 0a 0a 0a 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |....----|--------|
|00005370| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005380| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005390| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000053a0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0a 0a 53 75 62 6a |--------|--..Subj|
|000053b0| 65 63 74 3a 20 31 34 29 | 20 48 6f 77 20 64 6f 20 |ect: 14)| How do |
|000053c0| 49 20 65 6e 6c 61 72 67 | 65 2f 73 68 61 72 70 65 |I enlarg|e/sharpe|
|000053d0| 6e 2f 66 75 7a 7a 20 61 | 20 62 69 74 6d 61 70 3f |n/fuzz a| bitmap?|
|000053e0| 0a 0a 0a 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |...-----|--------|
|000053f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005400| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005410| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005420| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 0a 0a 53 75 62 6a 65 |--------|-..Subje|
|00005430| 63 74 3a 20 31 35 29 20 | 48 6f 77 20 64 6f 20 49 |ct: 15) |How do I|
|00005440| 20 6d 61 70 20 61 20 74 | 65 78 74 75 72 65 20 6f | map a t|exture o|
|00005450| 6e 20 74 6f 20 61 20 73 | 68 61 70 65 3f 0a 0a 20 |n to a s|hape?.. |
|00005460| 20 20 20 50 61 75 6c 20 | 53 2e 20 48 65 63 6b 62 | Paul |S. Heckb|
|00005470| 65 72 74 2c 20 22 53 75 | 72 76 65 79 20 6f 66 20 |ert, "Su|rvey of |
|00005480| 54 65 78 74 75 72 65 20 | 4d 61 70 70 69 6e 67 22 |Texture |Mapping"|
|00005490| 2c 20 49 45 45 45 20 43 | 6f 6d 70 75 74 65 72 0a |, IEEE C|omputer.|
|000054a0| 20 20 20 20 47 72 61 70 | 68 69 63 73 20 61 6e 64 | Grap|hics and|
|000054b0| 20 41 70 70 6c 69 63 61 | 74 69 6f 6e 73 20 56 36 | Applica|tions V6|
|000054c0| 2c 20 23 31 31 2c 20 4e | 6f 76 2e 20 31 39 38 36 |, #11, N|ov. 1986|
|000054d0| 2c 20 70 70 20 35 36 2d | 36 37 20 72 65 76 69 73 |, pp 56-|67 revis|
|000054e0| 65 64 0a 20 20 20 20 66 | 72 6f 6d 20 47 72 61 70 |ed. f|rom Grap|
|000054f0| 68 69 63 73 20 49 6e 74 | 65 72 66 61 63 65 20 27 |hics Int|erface '|
|00005500| 38 36 20 76 65 72 73 69 | 6f 6e 0a 0a 20 20 20 20 |86 versi|on.. |
|00005510| 45 72 69 63 20 41 2e 20 | 42 69 65 72 20 61 6e 64 |Eric A. |Bier and|
|00005520| 20 4b 65 6e 6e 65 74 68 | 20 52 2e 20 53 6c 6f 61 | Kenneth| R. Sloa|
|00005530| 6e 2c 20 4a 72 2e 2c 20 | 22 54 77 6f 2d 50 61 72 |n, Jr., |"Two-Par|
|00005540| 74 20 54 65 78 74 75 72 | 65 0a 20 20 20 20 4d 61 |t Textur|e. Ma|
|00005550| 70 70 69 6e 67 73 22 2c | 20 49 45 45 45 20 43 6f |ppings",| IEEE Co|
|00005560| 6d 70 75 74 65 72 20 47 | 72 61 70 68 69 63 73 20 |mputer G|raphics |
|00005570| 61 6e 64 20 41 70 70 6c | 69 63 61 74 69 6f 6e 73 |and Appl|ications|
|00005580| 20 56 36 20 23 39 2c 20 | 53 65 70 74 2e 0a 20 20 | V6 #9, |Sept.. |
|00005590| 20 20 31 39 38 36 2c 20 | 70 70 20 34 30 2d 35 33 | 1986, |pp 40-53|
|000055a0| 20 28 70 72 6f 6a 65 63 | 74 69 6f 6e 20 70 61 72 | (projec|tion par|
|000055b0| 61 6d 65 74 65 72 69 7a | 61 74 69 6f 6e 73 29 0a |ameteriz|ations).|
|000055c0| 0a 0a 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |..------|--------|
|000055d0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000055e0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|000055f0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005600| 2d 2d 2d 2d 2d 2d 2d 2d | 0a 0a 53 75 62 6a 65 63 |--------|..Subjec|
|00005610| 74 3a 20 31 36 29 20 48 | 6f 77 20 64 6f 20 49 20 |t: 16) H|ow do I |
|00005620| 66 69 6e 64 20 74 68 65 | 20 61 72 65 61 2f 6f 72 |find the| area/or|
|00005630| 69 65 6e 74 61 74 69 6f | 6e 20 6f 66 20 61 20 70 |ientatio|n of a p|
|00005640| 6f 6c 79 67 6f 6e 3f 0a | 0a 20 20 20 20 43 6f 6d |olygon?.|. Com|
|00005650| 70 75 74 65 20 74 68 65 | 20 73 69 67 6e 65 64 20 |pute the| signed |
|00005660| 61 72 65 61 2e 20 20 54 | 68 65 20 6f 72 69 65 6e |area. T|he orien|
|00005670| 74 61 74 69 6f 6e 20 69 | 73 20 63 6f 75 6e 74 65 |tation i|s counte|
|00005680| 72 2d 63 6c 6f 63 6b 77 | 69 73 65 20 69 66 0a 20 |r-clockw|ise if. |
|00005690| 20 20 20 74 68 69 73 20 | 61 72 65 61 20 69 73 20 | this |area is |
|000056a0| 70 6f 73 69 74 69 76 65 | 2e 20 20 54 68 65 72 65 |positive|. There|
|000056b0| 27 73 20 61 20 47 65 6d | 20 6f 6e 20 63 6f 6d 70 |'s a Gem| on comp|
|000056c0| 75 74 69 6e 67 20 73 69 | 67 6e 65 64 20 61 72 65 |uting si|gned are|
|000056d0| 61 73 2e 0a 0a 20 20 20 | 20 41 20 73 6c 69 67 68 |as... | A sligh|
|000056e0| 74 6c 79 20 66 61 73 74 | 65 72 20 6d 65 74 68 6f |tly fast|er metho|
|000056f0| 64 20 69 73 20 62 61 73 | 65 64 20 6f 6e 20 74 68 |d is bas|ed on th|
|00005700| 65 20 6f 62 73 65 72 76 | 61 74 69 6f 6e 20 74 68 |e observ|ation th|
|00005710| 61 74 20 69 74 20 69 73 | 6e 27 74 0a 20 20 20 20 |at it is|n't. |
|00005720| 6e 65 63 65 73 73 61 72 | 79 20 74 6f 20 63 6f 6d |necessar|y to com|
|00005730| 70 75 74 65 20 74 68 65 | 20 61 72 65 61 2e 20 20 |pute the| area. |
|00005740| 4f 6e 65 20 63 61 6e 20 | 66 69 6e 64 20 74 68 65 |One can |find the|
|00005750| 20 6c 6f 77 65 73 74 2c | 20 72 69 67 68 74 6d 6f | lowest,| rightmo|
|00005760| 73 74 0a 20 20 20 20 70 | 6f 69 6e 74 20 6f 66 20 |st. p|oint of |
|00005770| 74 68 65 20 70 6f 6c 79 | 67 6f 6e 2c 20 61 6e 64 |the poly|gon, and|
|00005780| 20 74 68 65 6e 20 74 61 | 6b 65 20 74 68 65 20 63 | then ta|ke the c|
|00005790| 72 6f 73 73 20 70 72 6f | 64 75 63 74 20 6f 66 20 |ross pro|duct of |
|000057a0| 74 68 65 20 65 64 67 65 | 73 0a 20 20 20 20 66 6f |the edge|s. fo|
|000057b0| 72 65 20 61 6e 64 20 61 | 66 74 20 6f 66 20 69 74 |re and a|ft of it|
|000057c0| 2e 20 20 42 6f 74 68 20 | 6d 65 74 68 6f 64 73 20 |. Both |methods |
|000057d0| 61 72 65 20 4f 28 6e 29 | 20 66 6f 72 20 6e 20 76 |are O(n)| for n v|
|000057e0| 65 72 74 69 63 65 73 2c | 20 62 75 74 20 69 74 0a |ertices,| but it.|
|000057f0| 20 20 20 20 64 6f 65 73 | 20 73 65 65 6d 20 61 20 | does| seem a |
|00005800| 77 61 73 74 65 20 74 6f | 20 61 64 64 20 75 70 20 |waste to| add up |
|00005810| 74 68 65 20 74 6f 74 61 | 6c 20 61 72 65 61 20 77 |the tota|l area w|
|00005820| 68 65 6e 20 61 20 73 69 | 6e 67 6c 65 20 63 72 6f |hen a si|ngle cro|
|00005830| 73 73 0a 20 20 20 20 70 | 72 6f 64 75 63 74 20 28 |ss. p|roduct (|
|00005840| 6f 66 20 6a 75 73 74 20 | 74 68 65 20 72 69 67 68 |of just |the righ|
|00005850| 74 20 65 64 67 65 73 29 | 20 73 75 66 66 69 63 65 |t edges)| suffice|
|00005860| 73 2e 0a 0a 20 20 20 20 | 54 68 65 20 72 65 61 73 |s... |The reas|
|00005870| 6f 6e 20 74 68 61 74 20 | 74 68 65 20 6c 6f 77 65 |on that |the lowe|
|00005880| 73 74 2c 20 72 69 67 68 | 74 6d 6f 73 74 20 70 6f |st, righ|tmost po|
|00005890| 69 6e 74 20 77 6f 72 6b | 73 20 69 73 20 74 68 61 |int work|s is tha|
|000058a0| 74 20 74 68 65 0a 20 20 | 20 20 69 6e 74 65 72 6e |t the. | intern|
|000058b0| 61 6c 20 61 6e 67 6c 65 | 20 61 74 20 74 68 69 73 |al angle| at this|
|000058c0| 20 76 65 72 74 65 78 20 | 69 73 20 6e 65 63 65 73 | vertex |is neces|
|000058d0| 73 61 72 69 6c 79 20 63 | 6f 6e 76 65 78 2c 20 73 |sarily c|onvex, s|
|000058e0| 74 72 69 63 74 6c 79 20 | 6c 65 73 73 0a 20 20 20 |trictly |less. |
|000058f0| 20 74 68 61 6e 20 70 69 | 20 28 65 76 65 6e 20 69 | than pi| (even i|
|00005900| 66 20 74 68 65 72 65 20 | 61 72 65 20 73 65 76 65 |f there |are seve|
|00005910| 72 61 6c 20 65 71 75 61 | 6c 6c 79 2d 6c 6f 77 65 |ral equa|lly-lowe|
|00005920| 73 74 20 70 6f 69 6e 74 | 73 29 2e 0a 0a 20 20 20 |st point|s)... |
|00005930| 20 54 68 65 20 6b 65 79 | 20 66 6f 72 6d 75 6c 61 | The key| formula|
|00005940| 20 69 73 20 74 68 69 73 | 3a 0a 0a 20 20 20 20 20 | is this|:.. |
|00005950| 20 20 20 49 66 20 74 68 | 65 20 63 6f 6f 72 64 69 | If th|e coordi|
|00005960| 6e 61 74 65 73 20 6f 66 | 20 76 65 72 74 65 78 20 |nates of| vertex |
|00005970| 76 5f 69 20 61 72 65 20 | 78 5f 69 20 61 6e 64 20 |v_i are |x_i and |
|00005980| 79 5f 69 2c 0a 20 20 20 | 20 20 20 20 20 74 77 69 |y_i,. | twi|
|00005990| 63 65 20 74 68 65 20 61 | 72 65 61 20 6f 66 20 61 |ce the a|rea of a|
|000059a0| 20 70 6f 6c 79 67 6f 6e | 20 69 73 20 67 69 76 65 | polygon| is give|
|000059b0| 6e 20 62 79 0a 0a 20 20 | 20 20 20 20 20 20 32 20 |n by.. | 2 |
|000059c0| 41 28 20 50 20 29 20 3d | 20 73 75 6d 5f 7b 69 3d |A( P ) =| sum_{i=|
|000059d0| 30 7d 5e 7b 6e 2d 31 7d | 20 28 78 5f 69 20 79 5f |0}^{n-1}| (x_i y_|
|000059e0| 7b 69 2b 31 7d 20 2d 20 | 79 5f 69 20 78 5f 7b 69 |{i+1} - |y_i x_{i|
|000059f0| 2b 31 7d 29 2e 0a 0a 20 | 20 20 20 52 65 66 65 72 |+1})... | Refer|
|00005a00| 65 6e 63 65 3a 0a 0a 20 | 20 20 20 5b 4f 27 20 52 |ence:.. | [O' R|
|00005a10| 6f 75 72 6b 65 5d 20 70 | 70 2e 20 31 38 2d 32 37 |ourke] p|p. 18-27|
|00005a20| 2e 0a 0a 0a 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |....----|--------|
|00005a30| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005a40| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005a50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005a60| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0a 0a 53 75 62 6a |--------|--..Subj|
|00005a70| 65 63 74 3a 20 31 37 29 | 20 48 6f 77 20 64 6f 20 |ect: 17)| How do |
|00005a80| 49 20 66 69 6e 64 20 69 | 66 20 61 20 70 6f 69 6e |I find i|f a poin|
|00005a90| 74 20 6c 69 65 73 20 77 | 69 74 68 69 6e 20 61 20 |t lies w|ithin a |
|00005aa0| 70 6f 6c 79 67 6f 6e 3f | 0a 0a 20 20 20 20 41 20 |polygon?|.. A |
|00005ab0| 71 75 69 63 6b 20 63 6f | 6d 6d 65 6e 74 20 2d 20 |quick co|mment - |
|00005ac0| 74 68 65 20 63 6f 64 65 | 20 69 6e 20 74 68 65 20 |the code| in the |
|00005ad0| 53 65 64 67 65 77 69 63 | 6b 20 62 6f 6f 6b 20 41 |Sedgewic|k book A|
|00005ae0| 6c 67 6f 72 69 74 68 6d | 73 20 69 73 0a 20 20 20 |lgorithm|s is. |
|00005af0| 20 77 72 6f 6e 67 2e 0a | 0a 20 20 20 20 54 68 65 | wrong..|. The|
|00005b00| 20 73 68 6f 72 74 20 61 | 6e 73 77 65 72 2c 20 66 | short a|nswer, f|
|00005b10| 6f 72 20 74 68 65 20 46 | 41 51 2c 20 63 6f 75 6c |or the F|AQ, coul|
|00005b20| 64 20 62 65 3a 0a 0a 20 | 20 20 20 69 6e 74 20 70 |d be:.. | int p|
|00005b30| 6e 70 6f 6c 79 28 69 6e | 74 20 6e 70 6f 6c 2c 20 |npoly(in|t npol, |
|00005b40| 66 6c 6f 61 74 20 2a 78 | 70 2c 20 66 6c 6f 61 74 |float *x|p, float|
|00005b50| 20 2a 79 70 2c 20 66 6c | 6f 61 74 20 78 2c 20 66 | *yp, fl|oat x, f|
|00005b60| 6c 6f 61 74 20 79 29 0a | 20 20 20 20 7b 0a 20 20 |loat y).| {. |
|00005b70| 20 20 20 20 69 6e 74 20 | 69 2c 20 6a 2c 20 63 20 | int |i, j, c |
|00005b80| 3d 20 30 3b 0a 20 20 20 | 20 20 20 66 6f 72 20 28 |= 0;. | for (|
|00005b90| 69 20 3d 20 30 2c 20 6a | 20 3d 20 6e 70 6f 6c 2d |i = 0, j| = npol-|
|00005ba0| 31 3b 20 69 20 3c 20 6e | 70 6f 6c 3b 20 6a 20 3d |1; i < n|pol; j =|
|00005bb0| 20 69 2b 2b 29 20 7b 0a | 20 20 20 20 20 20 20 20 | i++) {.| |
|00005bc0| 69 66 20 28 28 28 28 79 | 70 5b 69 5d 3c 3d 79 29 |if ((((y|p[i]<=y)|
|00005bd0| 20 26 26 20 28 79 3c 79 | 70 5b 6a 5d 29 29 20 7c | && (y<y|p[j])) ||
|00005be0| 7c 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 ||. | (|
|00005bf0| 28 79 70 5b 6a 5d 3c 3d | 79 29 20 26 26 20 28 79 |(yp[j]<=|y) && (y|
|00005c00| 3c 79 70 5b 69 5d 29 29 | 29 20 26 26 0a 20 20 20 |<yp[i]))|) &&. |
|00005c10| 20 20 20 20 20 20 20 20 | 20 28 78 20 3c 20 28 78 | | (x < (x|
|00005c20| 70 5b 6a 5d 20 2d 20 78 | 70 5b 69 5d 29 20 2a 20 |p[j] - x|p[i]) * |
|00005c30| 28 79 20 2d 20 79 70 5b | 69 5d 29 20 2f 20 28 79 |(y - yp[|i]) / (y|
|00005c40| 70 5b 6a 5d 20 2d 20 79 | 70 5b 69 5d 29 20 2b 20 |p[j] - y|p[i]) + |
|00005c50| 78 70 5b 69 5d 29 29 0a | 20 20 20 20 20 20 20 20 |xp[i])).| |
|00005c60| 20 20 63 20 3d 20 21 63 | 3b 0a 20 20 20 20 20 20 | c = !c|;. |
|00005c70| 7d 0a 20 20 20 20 20 20 | 72 65 74 75 72 6e 20 63 |}. |return c|
|00005c80| 3b 0a 20 20 20 20 7d 0a | 0a 20 20 20 20 54 68 69 |;. }.|. Thi|
|00005c90| 73 20 63 6f 64 65 20 69 | 73 20 66 72 6f 6d 20 57 |s code i|s from W|
|00005ca0| 6d 2e 20 52 61 6e 64 6f | 6c 70 68 20 46 72 61 6e |m. Rando|lph Fran|
|00005cb0| 6b 6c 69 6e 2c 20 77 72 | 66 40 65 63 73 65 2e 72 |klin, wr|f@ecse.r|
|00005cc0| 70 69 2e 65 64 75 2c 20 | 61 0a 20 20 20 20 70 72 |pi.edu, |a. pr|
|00005cd0| 6f 66 65 73 73 6f 72 20 | 61 74 20 52 50 49 2c 20 |ofessor |at RPI, |
|00005ce0| 77 69 74 68 20 73 6f 6d | 65 20 6d 69 6e 6f 72 20 |with som|e minor |
|00005cf0| 6d 6f 64 69 66 69 63 61 | 74 69 6f 6e 73 20 66 6f |modifica|tions fo|
|00005d00| 72 20 73 70 65 65 64 20 | 62 79 20 6d 65 2e 0a 20 |r speed |by me.. |
|00005d10| 20 20 20 41 20 67 6f 6f | 64 20 72 65 66 65 72 65 | A goo|d refere|
|00005d20| 6e 63 65 20 66 6f 72 20 | 74 68 69 73 20 70 72 6f |nce for |this pro|
|00005d30| 62 6c 65 6d 20 77 69 6c | 6c 20 62 65 3a 0a 0a 20 |blem wil|l be:.. |
|00005d40| 20 20 20 52 65 66 65 72 | 65 6e 63 65 73 3a 0a 0a | Refer|ences:..|
|00005d50| 20 20 20 20 5b 4f 27 52 | 6f 75 72 6b 65 5d 20 70 | [O'R|ourke] p|
|00005d60| 70 2e 20 32 33 33 2d 32 | 33 38 0a 20 20 20 20 5b |p. 233-2|38. [|
|00005d70| 47 65 6d 73 20 49 56 5d | 20 20 70 70 2e 20 32 33 |Gems IV]| pp. 23|
|00005d80| 2d 34 35 0a 20 20 20 20 | 5b 47 6c 61 73 73 6e 65 |-45. |[Glassne|
|00005d90| 72 3a 52 61 79 54 72 61 | 63 69 6e 67 5d 0a 0a 0a |r:RayTra|cing]...|
|00005da0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005db0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005dc0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005dd0| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005de0| 2d 2d 2d 2d 2d 2d 0a 0a | 53 75 62 6a 65 63 74 3a |------..|Subject:|
|00005df0| 20 31 38 29 20 48 6f 77 | 20 64 6f 20 49 20 66 69 | 18) How| do I fi|
|00005e00| 6e 64 20 74 68 65 20 69 | 6e 74 65 72 73 65 63 74 |nd the i|ntersect|
|00005e10| 69 6f 6e 20 6f 66 20 74 | 77 6f 20 63 6f 6e 76 65 |ion of t|wo conve|
|00005e20| 78 20 70 6f 6c 79 67 6f | 6e 73 3f 0a 0a 20 20 20 |x polygo|ns?.. |
|00005e30| 20 5b 4f 27 52 6f 75 72 | 6b 65 5d 20 70 70 2e 20 | [O'Rour|ke] pp. |
|00005e40| 32 34 32 2d 32 35 32 0a | 0a 0a 2d 2d 2d 2d 2d 2d |242-252.|..------|
|00005e50| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005e60| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005e70| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005e80| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00005e90| 0a 0a 53 75 62 6a 65 63 | 74 3a 20 31 39 29 20 48 |..Subjec|t: 19) H|
|00005ea0| 6f 77 20 64 6f 20 49 20 | 64 65 74 65 63 74 20 61 |ow do I |detect a|
|00005eb0| 20 27 63 6f 72 6e 65 72 | 27 20 69 6e 20 61 20 63 | 'corner|' in a c|
|00005ec0| 6f 6c 6c 65 63 74 69 6f | 6e 20 6f 66 20 70 6f 69 |ollectio|n of poi|
|00005ed0| 6e 74 73 3f 0a 0a 20 20 | 20 20 46 6f 72 20 74 68 |nts?.. | For th|
|00005ee0| 65 20 67 65 6e 65 72 61 | 6c 20 73 6f 6c 75 74 69 |e genera|l soluti|
|00005ef0| 6f 6e 20 74 6f 20 74 68 | 65 20 70 72 6f 62 6c 65 |on to th|e proble|
|00005f00| 6d 20 67 65 74 20 41 74 | 61 20 45 74 65 6d 61 64 |m get At|a Etemad|
|00005f10| 69 27 73 20 73 6f 66 74 | 77 61 72 65 0a 20 20 20 |i's soft|ware. |
|00005f20| 20 70 61 63 6b 61 67 65 | 20 61 6e 64 20 61 73 73 | package| and ass|
|00005f30| 6f 63 69 61 74 65 64 20 | 20 70 61 70 65 72 73 20 |ociated | papers |
|00005f40| 66 72 6f 6d 20 6f 6e 65 | 20 6f 66 20 74 68 65 20 |from one| of the |
|00005f50| 61 64 64 72 65 73 73 65 | 73 20 62 65 6c 6f 77 2e |addresse|s below.|
|00005f60| 0a 20 20 20 20 49 74 27 | 73 20 76 65 72 79 20 66 |. It'|s very f|
|00005f70| 61 73 74 20 61 6e 64 20 | 64 65 74 65 63 74 73 20 |ast and |detects |
|00005f80| 70 6f 6c 79 67 6f 6e 73 | 20 74 6f 6f 2e 0a 0a 20 |polygons| too... |
|00005f90| 20 20 20 66 74 70 3a 2f | 2f 70 65 69 70 61 2e 65 | ftp:/|/peipa.e|
|00005fa0| 73 73 65 78 2e 61 63 2e | 75 6b 2f 69 70 61 2f 73 |ssex.ac.|uk/ipa/s|
|00005fb0| 72 63 2f 70 72 6f 63 65 | 73 73 0a 20 20 20 20 66 |rc/proce|ss. f|
|00005fc0| 74 70 3a 2f 2f 66 74 70 | 2e 74 65 6c 65 6f 73 2e |tp://ftp|.teleos.|
|00005fd0| 63 6f 6d 2f 56 49 53 49 | 4f 4e 2d 4c 49 53 54 2d |com/VISI|ON-LIST-|
|00005fe0| 41 52 43 48 49 56 45 2f | 53 48 41 52 45 57 41 52 |ARCHIVE/|SHAREWAR|
|00005ff0| 45 0a 0a 0a 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |E...----|--------|
|00006000| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00006010| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00006020| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00006030| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0a 0a 53 75 62 6a |--------|--..Subj|
|00006040| 65 63 74 3a 20 32 30 29 | 20 48 6f 77 20 64 6f 20 |ect: 20)| How do |
|00006050| 49 20 67 65 6e 65 72 61 | 74 65 20 61 20 63 69 72 |I genera|te a cir|
|00006060| 63 6c 65 20 74 68 72 6f | 75 67 68 20 74 68 72 65 |cle thro|ugh thre|
|00006070| 65 20 70 6f 69 6e 74 73 | 3f 0a 0a 20 20 20 20 4c |e points|?.. L|
|00006080| 65 74 20 74 68 65 20 74 | 68 72 65 65 20 67 69 76 |et the t|hree giv|
|00006090| 65 6e 20 70 6f 69 6e 74 | 73 20 62 65 20 61 2c 20 |en point|s be a, |
|000060a0| 62 2c 20 63 2e 20 20 55 | 73 65 20 5f 30 20 61 6e |b, c. U|se _0 an|
|000060b0| 64 20 5f 31 20 74 6f 20 | 72 65 70 72 65 73 65 6e |d _1 to |represen|
|000060c0| 74 0a 20 20 20 20 78 20 | 61 6e 64 20 79 20 63 6f |t. x |and y co|
|000060d0| 6f 72 64 69 6e 61 74 65 | 73 2e 20 54 68 65 20 63 |ordinate|s. The c|
|000060e0| 6f 6f 72 64 69 6e 61 74 | 65 73 20 6f 66 20 74 68 |oordinat|es of th|
|000060f0| 65 20 63 65 6e 74 65 72 | 20 70 3d 28 70 5f 30 2c |e center| p=(p_0,|
|00006100| 70 5f 31 29 20 6f 66 0a | 20 20 20 20 74 68 65 20 |p_1) of.| the |
|00006110| 63 69 72 63 6c 65 20 64 | 65 74 65 72 6d 69 6e 65 |circle d|etermine|
|00006120| 64 20 62 79 20 61 2c 20 | 62 2c 20 61 6e 64 20 63 |d by a, |b, and c|
|00006130| 20 61 72 65 3a 0a 0a 20 | 20 20 20 20 20 20 20 20 | are:.. | |
|00006140| 20 20 20 70 5f 30 20 3d | 0a 20 20 20 20 20 20 20 | p_0 =|. |
|00006150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 20 62 | | ( b|
|00006160| 5f 31 20 61 5f 30 5e 32 | 0a 20 20 20 20 20 20 20 |_1 a_0^2|. |
|00006170| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 63 | | - c|
|00006180| 5f 31 20 61 5f 30 5e 32 | 0a 20 20 20 20 20 20 20 |_1 a_0^2|. |
|00006190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 62 | | - b|
|000061a0| 5f 31 5e 32 20 61 5f 31 | 0a 20 20 20 20 20 20 20 |_1^2 a_1|. |
|000061b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2b 20 63 | | + c|
|000061c0| 5f 31 5e 32 20 61 5f 31 | 0a 20 20 20 20 20 20 20 |_1^2 a_1|. |
|000061d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2b 20 62 | | + b|
|000061e0| 5f 30 5e 32 20 63 5f 31 | 0a 20 20 20 20 20 20 20 |_0^2 c_1|. |
|000061f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2b 20 61 | | + a|
|00006200| 5f 31 5e 32 20 62 5f 31 | 0a 20 20 20 20 20 20 20 |_1^2 b_1|. |
|00006210| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2b 20 63 | | + c|
|00006220| 5f 30 5e 32 20 61 5f 31 | 0a 20 20 20 20 20 20 20 |_0^2 a_1|. |
|00006230| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 63 | | - c|
|00006240| 5f 31 5e 32 20 62 5f 31 | 0a 20 20 20 20 20 20 20 |_1^2 b_1|. |
|00006250| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 63 | | - c|
|00006260| 5f 30 5e 32 20 62 5f 31 | 0a 20 20 20 20 20 20 20 |_0^2 b_1|. |
|00006270| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 62 | | - b|
|00006280| 5f 30 5e 32 20 61 5f 31 | 0a 20 20 20 20 20 20 20 |_0^2 a_1|. |
|00006290| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2b 20 62 | | + b|
|000062a0| 5f 31 5e 32 20 63 5f 31 | 0a 20 20 20 20 20 20 20 |_1^2 c_1|. |
|000062b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2d 20 61 | | - a|
|000062c0| 5f 31 5e 32 20 63 5f 31 | 20 29 0a 20 20 20 20 20 |_1^2 c_1| ). |
|000062d0| 20 20 20 20 20 20 20 20 | 20 20 20 2f 20 44 0a 0a | | / D..|
|000062e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 70 5f 31 20 | | p_1 |
|000062f0| 3d 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |=. | |
|00006300| 20 20 20 20 20 20 28 20 | 61 5f 30 5e 32 20 63 5f | ( |a_0^2 c_|
|00006310| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|00006320| 20 20 20 20 20 20 2b 20 | 61 5f 31 5e 32 20 63 5f | + |a_1^2 c_|
|00006330| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|00006340| 20 20 20 20 20 20 2b 20 | 62 5f 30 5e 32 20 61 5f | + |b_0^2 a_|
|00006350| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|00006360| 20 20 20 20 20 20 2d 20 | 62 5f 30 5e 32 20 63 5f | - |b_0^2 c_|
|00006370| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|00006380| 20 20 20 20 20 20 2b 20 | 62 5f 31 5e 32 20 61 5f | + |b_1^2 a_|
|00006390| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|000063a0| 20 20 20 20 20 20 2d 20 | 62 5f 31 5e 32 20 63 5f | - |b_1^2 c_|
|000063b0| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|000063c0| 20 20 20 20 20 20 2d 20 | 61 5f 30 5e 32 20 62 5f | - |a_0^2 b_|
|000063d0| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
|000063e0| 20 20 20 20 20 20 2d 20 | 61 5f 31 5e 32 20 62 5f | - |a_1^2 b_|
|000063f0| 30 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |0. | |
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
